hdu3874一维树状数组+离线算法

这题开始一直不会，查解题报告，都看不懂，后来还是自己想明白了……其实这个题目的难点就在于重复值不能重复算（假设没有重复值就是一道很水的树状数组题了，甚至都可以不用树状数组），所以这题突破点就是消除重复值带来的影响。如何消除呢？其实也不难。我们先局部地看这个问题，数据不是一次性加入树状数组里，而是一个个地加。假设有两个查询(1, y1)和(x2, y2)其中y1<y2。假设[1, y1]之间没有重复的数，那么我们把这些数插入一个树状数组里就能解决问题（logn时间查出结果）。然后到了操作(x2,y2)，因为y2比y1大，在y1到y2之间可能有些数在[1,y1]已经出现过了，那么我们如何处理呢？没错！删掉前面那个，保留当前这个！（这个不理解的慢慢想，想清楚别的就简单了）这样我们又解决了(x2,y2)的查询，并且树状数组里维护的依然没有重复的数，依此类推，就能解决问题。当然，这是需要离线做的，先把所有数和操作都存起来，把操作按y从小到大排序，按排好的顺序一个个地处理每个操作。

/*
 * hdu3874/win.cpp
 * Created on: 2012-11-1
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 50100;
const int MAXQ = 2000010;
typedef long long typec;
typedef struct Query{
    int pos, x, y;
    typec result;
}Query;
inline bool cmppos(const Query &q1, const Query &q2) {
    return q1.pos < q2.pos;
}
inline bool cmpy(const Query &q1, const Query &q2) {
    return q1.y < q2.y;
}
inline int lowbit(int x) {
    return x & (-x);
}
int N, Q;
Query query[MAXQ];
map<int, int> lastpos;
typec data[MAXN];//存储数据，下标从1开始
int inputdata[MAXN];
//查询data[1...pos]的和
typec sum(int pos) {
    typec ret = 0;
    for(int i = pos; i > 0; i -= lowbit(i)) {
        ret += data[i];
    }
    return ret;
}
//修改data[pos]的值，在原来基础上加value
void modify(int pos, typec value) {
    for (int i = pos; i <= N; i += lowbit(i)) {
        data[i] += value;
    }
}
void insert(int pos, int value) {
    if(lastpos[value] != 0) {
        modify(lastpos[value], -value);
    }
    lastpos[value] = pos;
    modify(pos, value);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        lastpos.clear();
        scanf("%d", &N);
        for(int i = 1; i <= N; i++) {
            scanf("%d", &inputdata[i]);
        }
        scanf("%d", &Q);
        for(int i = 0; i < Q; i++) {
            scanf("%d%d", &query[i].x, &query[i].y);
            query[i].pos = i;
        }
        sort(query, query + Q, cmpy);
        fill(data, data + N + 1, 0);
        int I = 1;
        for(int i = 0; i < Q; i++) {
            while(I <= query[i].y && I <= N) {
                insert(I, inputdata[I]);
                I++;
            }
            query[i].result = sum(query[i].y) - sum(query[i].x - 1);
        }
        sort(query, query + Q, cmppos);
        for(int i = 0; i < Q; i++) {
            printf("%I64d\n", query[i].result);
        }
    }
    return 0;
}