首页 > 代码库 > HDU 3333 Turing Tree 树状数组 离线查询

HDU 3333 Turing Tree 树状数组 离线查询

2024-07-18 15:22:40   217人阅读

题意： 给你一个数列，然后有n个查询，问你给定区间中不同数字的和是多少。

思路还是比较难想的，起码对于蒟蒻我来说。

将区间按照先右端点，后左端点从小到大排序之后，对于每个查询，我只要维护每个数字出现的最后一次就可以了（这个结论稍微想一下就可以证明是正确的）。

然后就是简单的点更新，区间求和问题了～

#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 3e4 + 10;struct Seg {    int l,r,id;    LL ans;    Seg(int l,int r,int id): l(l),r(r),id(id) {}}; int n,val[maxn],last[maxn],m;VI num;vector<Seg> query;LL C[maxn];bool ext[maxn];bool cmp(const Seg &a,const Seg &b) {    if(a.r == b.r) return a.l < b.l;    return a.r < b.r;}bool cmp1(const Seg &a,const Seg &b) {    return a.id < b.id;}inline int lowbit(int x) {    return x & (-x);}void addv(int pos,LL v) {    while(pos <= n) {        C[pos] += v; pos += lowbit(pos);    }}LL ask_(int pos) {    LL ret = 0;    while(pos > 0) {        ret += C[pos]; pos -= lowbit(pos);    }    return ret;}LL ask(int l,int r) {    return ask_(r) - ask_(l - 1);}int getID(int Val) {    return lower_bound(num.begin(),num.end(),Val) - num.begin() + 1;}void solve() {    memset(C,0,sizeof(C));    memset(last,-1,sizeof(last));    int npos = 1;    for(int i = 0;i < m;i++) {        Seg &now = query[i];        while(npos <= now.r) {            int nowval = getID(val[npos]);            if(last[nowval] != -1) addv(last[nowval],-val[npos]);            last[nowval] = npos;            addv(npos,val[npos]);            npos++;        }        now.ans = ask(now.l,now.r);    }}int main() {    int T; scanf("%d",&T);    while(T--) {        query.clear();        num.clear();        int tmp; scanf("%d",&n);        for(int i = 1;i <= n;i++) {            scanf("%d",&val[i]); num.PB(val[i]);        }        sort(num.begin(),num.end());        num.erase(unique(num.begin(),num.end()),num.end());        scanf("%d",&m);        for(int i = 0;i < m;i++) {            int l,r; scanf("%d%d",&l,&r);            query.PB(Seg(l,r,i));        }        sort(query.begin(),query.end(),cmp);        solve();        sort(query.begin(),query.end(),cmp1);        for(int i = 0;i < m;i++) cout << query[i].ans << endl;    }    return 0;}

　　


联系
我们