Educational Codeforces Round 22 E. Army Creation(主席树)

题目链接：Educational Codeforces Round 22 E. Army Creation

题意：

给你n个数和一个数k，然后有q个询问.

每个询问有一个区间[l,r]，问你这个区间内在满足每一种数不超过k的情况下，最大能选多少个数出来。

强制在线。

题解：

一看就要用到主席树，和主席数求区间内有多少不同的数的个数处理方法相同。

依次将每个数插入，当这个数出现的个数等于k了，就把最前面的那个数删掉。

然后询问就访问root[r]就行了。

第一次写完数据结构没有调试一遍过样例,一遍AC,这感觉真爽。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 
 8 struct node{int l,r,sum;}T[N*40];
 9 int root[N],a[N],hd[N],cnt,ct[N];
10 vector<int>Q[N];
11 int n,k,q,l,r;
12 
13 void update(int l,int r,int &x,int y,int pos,int v)
14 {
15     T[x=++cnt]=T[y],T[cnt].sum+=v;
16     if(l==r)return;
17     int mid=(l+r)>>1;
18     if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos,v);
19     else update(mid+1,r,T[x].r,T[y].r,pos,v);
20 }
21 
22 int query(int l,int r,int L,int R,int rt)
23 {
24     if(L<=l&&r<=R)return T[rt].sum;
25     int mid=l+r>>1,an=0;
26     if(L<=mid)an+=query(l,mid,L,R,T[rt].l);
27     if(R>mid)an+=query(mid+1,r,L,R,T[rt].r);
28     return an;
29 }
30 
31 int main()
32 {
33     scanf("%d%d",&n,&k);
34     F(i,1,n)scanf("%d",a+i);
35     F(i,1,n)
36     {
37         update(1,n,root[i],root[i-1],i,1);
38         Q[a[i]].push_back(i);
39         if(ct[a[i]]==k)
40         {
41             int x=Q[a[i]][hd[a[i]]++];
42             update(1,n,root[i],root[i],x,-1);
43         }else ct[a[i]]++;
44     }
45     int ans=0;
46     scanf("%d",&q);
47     while(q--)
48     {
49         scanf("%d%d",&l,&r);
50         l=(l+ans)%n+1,r=(r+ans)%n+1;
51         if(l>r)swap(l,r);
52         printf("%d
",ans=query(1,n,l,r,root[r]));
53     }
54     return 0;
55 }

View Code