【HDU】3333 Turing Tree

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef __int64 LL;
 6 #define MAXN 30010
 7 #define MAXM 100010
 8 int a[MAXN],b[MAXN],vis[MAXN];
 9 LL ans[MAXM],tree[MAXN<<2];
10 struct node
11 {
12     int left,right,pos;
13     friend bool operator<(node a,node b)
14     {
15         return a.right<b.right;
16     }
17 };
18 node p[MAXM];
19 inline void PushUp(int rt)
20 {
21     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
22 }
23 void Update(int x,int val,int L,int R,int rt)
24 {
25     if(L==R)
26         tree[rt]=val;
27     else
28     {
29         int mid=(L+R)>>1;
30         if(x<=mid)
31             Update(x,val,L,mid,rt<<1);
32         else
33             Update(x,val,mid+1,R,rt<<1|1);
34         PushUp(rt);
35     }
36 }
37 LL Query(int x,int y,int L,int R,int rt)
38 {
39     if(x<=L&&R<=y)
40         return tree[rt];
41     int mid=(L+R)>>1;
42     LL ans=0;
43     if(x<=mid)
44         ans+=Query(x,y,L,mid,rt<<1);
45     if(y>mid)
46         ans+=Query(x,y,mid+1,R,rt<<1|1);
47     return ans;
48 }
49 int main()
50 {
51     int t,n,m,i,j,k,q;
52     scanf("%d",&t);
53     while(t--)
54     {
55         scanf("%d",&n);
56         for(i=1;i<=n;i++)
57         {
58             scanf("%d",&a[i]);
59             b[i]=a[i];
60         }
61         sort(b+1,b+1+n);
62         m=unique(b+1,b+1+n)-b;
63         scanf("%d",&q);
64         for(i=0;i<q;i++)
65         {
66             scanf("%d%d",&p[i].left,&p[i].right);
67             p[i].pos=i;
68         }
69         sort(p,p+q);
70         memset(vis,0,sizeof(vis));
71         memset(tree,0,sizeof(tree));
72         for(i=1,j=0;i<=n;i++)
73         {
74             k=lower_bound(b+1,b+m,a[i])-b;
75             if(vis[k])
76                 Update(vis[k],0,1,n,1);
77             vis[k]=i;
78             Update(vis[k],a[i],1,n,1);
79             for(;j<q;j++)
80             {
81                 if(p[j].right<=i)
82                     ans[p[j].pos]=Query(p[j].left,p[j].right,1,n,1);
83                 else
84                     break;
85             }
86         }
87         for(i=0;i<q;i++)
88             printf("%I64d\n",ans[i]);
89     }
90     return 0;
91 }
新博客：www.zhixiangli.com