在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做,所以也出了一个字符串题:
给你一个字符串a,每次询问一段区间的贡献
贡献定义:
每次从这个区间中随机拿出一个字符x,然后把x从这个区间中删除,你要维护一个集合S
如果S为空,你rp减1
如果S中有一个元素不小于x,则你rp减1,清空S
之后将x插入S
由于你是大爷,平时做过的题考试都会考到,所以每次询问你搞完这段区间的字符之后最多还有多少rp?rp初始为0
询问之间不互相影响~
输入格式:
第一行两个数n,m,表示字符串长度与询问次数
之后一行n个数,表示字符串
由于你是大爷,所以字符集1e9
之后m行每行两个数,表示询问的左右区间
输出格式:
m行,每行一个数表示答案
输入样例#1:
3 3
3 3 3
3 3
3 3
3 3
输出样例#1:
-1
-1
-1
前4个点1s,后面的点4s
对于10%的数据,是样例
对于另外10%的数据,n,m <= 100
对于另外10%的数据,n,m <= 1000
对于另外10%的数据,n,m <= 10000
对于另外10%的数据,n,m <= 100000
对于100%的数据,n,m <= 200000
保证数据向某省省选day1T2一样sb,大家尽情用暴力水过题吧!
没事,你只要在一个好学校,就算这题只能拿到10分,也可以进队了
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstdlib>
6 #include<algorithm>
7 #include<vector>
8 #define hh 10
9 using namespace std;
10 const int MAXN=2000001;
11 void read(int & n)
12 {
13 char c='+';int x=0;bool flag=0;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+(c-48);c=getchar();}
18 flag==1?n=-x:n=x;
19 }
20 int n,m;
21 int pos[MAXN];
22 int base;
23 int rp=0;
24 struct node
25 {
26 int l,r,id;
27 }q[MAXN];
28 struct dr
29 {
30 int a,p;
31 }a[MAXN];
32 int comp(const node & a,const node &b)
33 {
34 if(pos[a.l]==pos[b.l])
35 return a.r<b.r;
36 else
37 return pos[a.l]<pos[b.l];
38 }
39 int cop(const dr &a,const dr &b)
40 {
41 return (a.a<b.a)||(a.a==b.a&&a.p<b.p);
42 }
43 int happen[MAXN];// 记录i出现了多少次
44 int cnt[MAXN];// 记录出现次数为j的有多少
45 int out[MAXN];
46 void dele(int p)
47 {
48 if(rp==happen[p]&&cnt[happen[p]+hh]==1)
49 rp--;
50 cnt[happen[p]+hh]--;
51 cnt[happen[p]+hh-1]++;
52 happen[p]--;
53 }
54 void add(int p)
55 {
56 if(rp==happen[p])
57 rp++;
58 cnt[happen[p]+hh]--;
59 cnt[happen[p]+hh+1]++;
60 happen[p]++;
61 }
62 int ls[MAXN];
63 void modui()
64 {
65 int ll=1,rr=0;
66 for(int i=1;i<=m;i++)
67 {
68 for(;ll<q[i].l;ll++)
69 dele(ls[ll]);
70 for(;ll>q[i].l;ll--)
71 add(ls[ll-1]);
72 for(;rr>q[i].r;rr--)
73 dele(ls[rr]);
74 for(;rr<q[i].r;rr++)
75 add(ls[rr+1]);
76 out[q[i].id]=-rp;
77 }
78 for(int i=1;i<=m;i++)
79 printf("%d\n",out[i]);
80 }
81 int main()
82 {
83 read(n);read(m);
84 base=sqrt(n);
85 for(int i=1;i<=n;i++)
86 read(a[i].a),a[i].p=i;
87 sort(a+1,a+n+1,cop);
88 int j;
89 for(int i=1,j=0;i<=n;i++)
90 {
91 if (i==1||a[i].a!=a[i-1].a) j++;
92 ls[a[i].p]=j;
93 }
94 //for(int i=1;i<=n;i++)
95 // pos[i]=(i-1)/base+1;
96 int sqt=0;
97 for ( sqt=1; sqt*sqt<=n; sqt++);
98
99 for (int i=1; i<=n; i++) pos[i]=i/sqt;
100
101 cnt[0]=j;
102 for(int i=1;i<=m;i++)
103 {
104 read(q[i].l);
105 read(q[i].r);
106 q[i].id=i;
107 }
108 sort(q+1,q+m+1,comp);
109 modui();
110 return 0;
111 }