对于 40% 的数据, 有 n≤1,000;
对于 100% 的数据, 有 n≤200,000,0<k≤50;
sol:NOIP 原题, 首先一段区间的最小值用 ST 表预处理一下 (n*logn), 之后对于每种颜色做一遍统计, 易知不合法的应该是一整段的, 认为那段个数有 Sum 个, 那么就去掉 Sum*(Sum-1)/2 种,(n*k)
- #include <bits/stdc++.h>
- using namespace std;
- inline int read()
- {
- int s=0,f=0;
- char ch=' ';
- while(!isdigit(ch))
- {
- f|=(ch=='-');
- ch=getchar();
- }
- while(isdigit(ch))
- {
- s=(s<<3)+(s<<1)+(ch^48);
- ch=getchar();
- }
- return (f)?(-s):(s);
- }
- #define R(x) x=read()
- const int N=200005;
- int Bin[23],Log[N];
- int n,k,p;
- int Cor[N],f[N][23];
- inline long long Solve(int C)
- {
- int i,Sum=0;
- long long ans=0;
- for(i=1;i<=n;i++) if(Cor[i]==C) Sum++;
- ans=1LL*((Sum*(Sum-1))>>1);
- int Pre=0;
- Sum=0;
- for(i=1;i<=n;i++) if(Cor[i]==C)
- {
- if(!Pre) {Pre=i; Sum++; continue;}
- int oo=Log[i-Pre+1];
- int Min=min(f[Pre][oo],f[i-Bin[oo]+1][oo]);
- if(Min>p) Sum++;
- else ans-=1LL*((Sum*(Sum-1))>>1),Pre=i,Sum=1;
- // printf("%d -- Pre=%d Sum=%d\n",i,Pre,Sum);
- }
- ans-=1LL*(Sum*(Sum-1))>>1;
- // printf("%d : %lld\n",C,ans);
- return ans;
- }
- int main()
- {
- int i,j;
- Bin[0]=1; for(i=1;i<=19;i++) Bin[i]=Bin[i-1]<<1;
- Log[0]=-1; for(i=1;i<N;i++) Log[i]=Log[i>>1]+1;
- R(n); R(k); R(p);
- for(i=1;i<=n;i++)
- {
- R(Cor[i]); R(f[i][0]);
- }
- for(i=1;i<=19;i++)
- {
- for(j=1;j+Bin[i]-1<=n;j++)
- {
- f[j][i]=min(f[j][i-1],f[j+Bin[i-1]][i-1]);
- }
- }
- long long ans=0;
- // Solve(1);
- for(i=0;i<k;i++) ans+=1LL*Solve(i);
- printf("%lld\n",ans);
- return 0;
- }
- /*
- input
- 5 2 3
- 0 5
- 1 3
- 0 2
- 1 4
- 1 5
- output
- 3
- */
- View Code
来源: http://www.bubuko.com/infodetail-2944820.html