HDU 3333 Turing Tree （离散化+离线处理+树状数组）

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

1
5
6
3
6

如果输入的a[i]没那么大的话，就和poj上的项链那题一模一样，这一题在那题的基础上加一个离散化处理。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <stack>
#include <cctype>
#include <algorithm>
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;
const int mod = 99999997;
const int MAX = 0x3f3f3f3f;
const int maxn = 50005;
int t, n, q;
int pre[maxn], last[maxn], in[maxn], tt[maxn], a[maxn];
LL c[maxn], ans[100055];
struct C {
    int l, r, pos;
} se[100055];
bool cmp(C x, C y) {
    return x.r < y.r;
}
int bs(int v, int x, int y) {
    while(x < y) {
        int m = (x+y) >> 1;
        if(in[m] >= v) y = m;
        else x = m + 1;
    }
    return x;
}
int main()
{
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; i++) {
            scanf("%d", &in[i]);
            tt[i+1] = in[i];
        }
        sort(in, in+n);
        int m = unique(in, in+n) - in;
        memset(pre, -1, sizeof(pre));
        memset(last, -1, sizeof(pre));
        memset(c, 0, sizeof(c));
        for(int i = 1; i <= n; i++) {
            a[i] = bs(tt[i], 0, m-1);
            if(pre[ a[i] ] != -1) last[i] = pre[ a[i] ];
            pre[ a[i] ] = i;
            for(int j = i; j <= n; j += j&-j) c[j] += tt[i];
        }
        cin >> q;
        for(int i = 0; i < q; i++) {
            scanf("%d%d", &se[i].l, &se[i].r);
            se[i].pos = i;
        }
        sort(se, se+q, cmp);
        int fr = 1;
        for(int i = 0; i < q; i++) {
            for(int j = fr; j <= se[i].r; j++) if(last[j] != -1)
                for(int k = last[j]; k <= n; k += k&-k) c[k] -= tt[j];
            LL sum1 = 0, sum2 = 0;
            for(int j = se[i].l - 1; j > 0; j -= j&-j) sum1 += c[j];
            for(int j = se[i].r; j > 0; j -= j&-j) sum2 += c[j];
            ans[ se[i].pos ] = sum2 - sum1;
            fr = se[i].r + 1;
        }
        for(int i = 0; i < q; i++) printf("%I64d\n", ans[i]);
    }
    return 0;
}

HDU 3333 Turing Tree （离散化+离线处理+树状数组）,布布扣,bubuko.com

HDU 3333 Turing Tree （离散化+离线处理+树状数组）

原文：http://blog.csdn.net/u013923947/article/details/38703089