转载请注明出处:http://tokitsukaze.live/

题目链接:https://www.nowcoder.com/acm/contest/139/J


题意:
给一个长度为n的序列和查询次数q。每次给出L和R,查询区间[1,L]和[R,n]中不同数的个数。


题解:
把序列复制一遍,就能查询连续的区间,然后就变成了主席树模板题。注意L>R的时候是查询整个序列。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

//由于FastIO太长,就不贴出来了
#include <bits/stdc++.h>
using namespace std;
void Main();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
Main();return 0;
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=1e9+7;
/********************************* head *********************************/
struct president_tree
{
int root[MAX],ls[40*MAX],rs[40*MAX],sum[40*MAX],tot,ql,qr,qv;
void init()
{
mem(root,0);
tot=1;
ls[0]=rs[0]=sum[0]=0;
}
int newnode(int x)
{
ls[tot]=ls[x];
rs[tot]=rs[x];
sum[tot]=sum[x];
return tot++;
}
void insert(int l,int r,int &id,int pre) //set(ql,ql,v)
{
id=newnode(pre);
sum[id]+=qv;
if(l==r) return;
int mid=(l+r)>>1;
if(ql<=mid) insert(l,mid,ls[id],ls[pre]);
else insert(mid+1,r,rs[id],rs[pre]);
}
int kindcnt(int l,int r,int id) //set(ql,qr)
{
if(ql<=l&&r<=qr) return sum[id];
int mid=(l+r)>>1;
int res=0;
if(ql<=mid) res+=kindcnt(l,mid,ls[id]);
if(qr>=mid+1) res+=kindcnt(mid+1,r,rs[id]);
return res;
}
int kthsmall(int l,int r,int id,int pre,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
int temp=sum[ls[id]]-sum[ls[pre]];
if(temp>=k) return kthsmall(l,mid,ls[id],ls[pre],k);
else return kthsmall(mid+1,r,rs[id],rs[pre],k-temp);
}
int kthbig(int l,int r,int id,int pre,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
int temp=sum[rs[id]]-sum[rs[pre]];
if(temp>=k) return kthbig(mid+1,r,rs[id],rs[pre],k);
else return kthbig(l,mid,ls[id],ls[pre],k-temp);
}
void set(int l,int r,int v=0){ql=l;qr=r;qv=v;}
}pt;
int a[MAX],last[MAX];
void Main()
{
int n,q,i,j,l,r;
while(read(n,q))
{
pt.init();
for(i=n,j=0;i<=2*n-1;i++,j++)
{
read(a[i]);
last[a[i]]=-1;
a[j]=a[i];
}
/* for(i=1;i<=2*n-1;i++) cout<<a[i]<<" ";
puts("");*/
for(i=2*n-1;i>=1;i--)
{
if(last[a[i]]==-1)
{
pt.set(i,i,1);
pt.insert(1,2*n-1,pt.root[i],pt.root[i+1]);
}
else
{
int tmp;
pt.set(last[a[i]],last[a[i]],-1);
pt.insert(1,2*n-1,tmp,pt.root[i+1]);
pt.set(i,i,1);
pt.insert(1,2*n-1,pt.root[i],tmp);
}
last[a[i]]=i;
}
while(q--)
{
read(l,r);
if(l<r-1)
{
l+=n-1;
r=n-(n-r+1);
swap(l,r);
// cout<<l<<" "<<r<<endl;
pt.set(l,r);
print(pt.kindcnt(1,2*n-1,pt.root[l]),'\n');
}
else
{
pt.set(1,2*n-1);
print(pt.kindcnt(1,2*n-1,pt.root[1]),'\n');
}
}
}
}