hdu 3874【Necklace】

看了别人的线段树的题解才知道思路的，然后用树状数组写出来

解决方案是：将询问的区间先存下来，然后按right边界排序

然后将排序后的询问按从左到右的顺序解决，从起始元素开始到right，依次插入到树状数组中去，如果之前有相同的数已经插入过（用hash判断即可），就从树状数组中（从先前那个相同的数的位置开始）删除加的那个数（即在树状数组中插入那个数的负值），然后再插入当前的这个数（从当前的数的这个位置）

然后就询问，将结果存在ans数组里面

提示：我用g++编译的，那个__int64_t要改成__int64后提交，后面的那个输出（打印结果的地方）要改成"%I64d"输出才行。。。一直WA，就是因为我用的long long

代码如下：

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 
  5 typedef __int64_t ll;
  6 const int maxN = 50000 + 10;
  7 const int maxM = 200000 + 10;
  8 
  9 int balls[maxN];
 10 ll ans[maxM];
 11 int hash[1000010];
 12 
 13 struct node
 14 {
 15     int l,r;
 16     int id;
 17     node(){}
 18     node(int left,int right,int curl)
 19     {
 20     l = left;
 21     r = right;
 22     id = curl;
 23     }
 24 }asks[maxM];
 25 
 26 ll tree[maxN];
 27 
 28 void update(int curl,int value,int n)
 29 {
 30     while(curl <= n)
 31     {
 32     tree[curl] += value;
 33     curl += (curl & (-curl));
 34     }
 35 }
 36 
 37 ll getSum(int curl)
 38 {
 39     ll sum = 0;
 40     while(curl > 0)
 41     {
 42     sum += tree[curl];
 43     curl -= (curl & (-curl));
 44     }
 45 
 46     return sum;
 47 }
 48 
 49 bool cmp(const node a,const node b)
 50 {
 51     if(a.r == b.r)
 52     {
 53         return a.l < b.l;
 54     }
 55     return a.r < b.r;
 56 }
 57 
 58 int main()
 59 {
 60     int cases;
 61     int n,m;
 62 
 63     scanf("%d",&cases);
 64 
 65     while(cases --)
 66     {
 67     scanf("%d",&n);
 68     for(int i = 1;i <= n;i ++)
 69     {
 70         scanf("%d",&balls[i]);
 71     }
 72 
 73     memset(hash,0,sizeof(hash));
 74     //memset(ans,0,sizeof(ans));
 75     memset(tree,0,sizeof(tree));
 76     scanf("%d",&m);
 77     int a,b;
 78     for(int i = 1;i <= m;i ++)
 79     {
 80        scanf("%d%d",&a,&b);
 81        if(a > b)
 82        {
 83            int t = a;
 84            a = b;
 85            b = t;
 86        }
 87        asks[i] = node(a,b,i);
 88     }
 89 
 90     std::sort(asks+1,asks+m+1,cmp);
 91 
 92     int run = 1;
 93     for(int i = 1;i <= m;i ++)
 94     {
 95         while(run <= asks[i].r)
 96         {
 97         if(hash[balls[run]])
 98         {
 99             update(hash[balls[run]],-balls[run],n);
100         }
101 
102         update(run,balls[run],n);
103         hash[balls[run]] = run;
104 
105         run ++;
106         }
107 
108         ans[asks[i].id] = getSum(asks[i].r) - getSum(asks[i].l - 1);
109     }
110 
111     for(int i = 1;i <= m;i ++)
112     {
113         printf("%lld\n",ans[i]);
114     }
115     }
116 
117     return 0;
118 }