2017.11.3 T1 2032
样例数据 输入
3 2 1 2 1 1 2 4 5
输出
2 6
分析：这道题为什么要放在T1……考得我怀疑人生。本来也只会暴力找，对于30%的数据我是这样的：先离散化，再二维数组记录所有颜色的在每个位置的前缀和，然后四层循环暴力查找。 而正解是：先离散化，再把每种颜色的每一个位置压入vector数组，然后查询到某两个颜色的时候就在这两个颜色的vector数组里查找，用一个sum，是第一种颜色就sum++，第二种颜色就sum–，这样sum相同地方之间的区域就是两种颜色出现次数一样的区间，计算贡献。
代码 我那30%都打错了，就不献丑了……这是100%
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cctype> #include<iomanip> #include<queue> #include<set> using namespace std; int getint() { int sum=0,f=1; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-48; return sum*f; } const int N=8005,M=500005; struct node { int x,y; }q[M]; int n,m,Q; int a[N],b[N],cnt[N<<1],exist[N<<1],ans[M]; vector<int>p[N]; bool comp(const node &a,const node &b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } void lsh()//把颜色、询问离散化并把颜色的位置放到vector里（先看solv会更好理解） { sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; for(int i=0;i<=m;++i) p[i].push_back(0);//先放个0进去，因为后面比较是比较i+1和j+1 for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b, p[a[i]].push_back(i); for(int i=0;i<=m;++i) p[i].push_back(n+1),p[i].push_back(n+2);//最后放两个n+1、n+2，同样是因为比较是比较i+1和j+1， //所以有一个会先走到n+1，然后的比较就要比较n+2了，不加n+2会爆炸 for(int i=1;i<=Q;i++)//把问题也离散化 { if(q[i].x>q[i].y)swap(q[i].x,q[i].y); if(b[lower_bound(b+1,b+m+1,q[i].x)-b]!=q[i].x)q[i].x=0;//如果问的颜色都不存在，就赋值为0，这样可以特判 else q[i].x=lower_bound(b+1,b+m+1,q[i].x)-b; if(b[lower_bound(b+1,b+m+1,q[i].y)-b]!=q[i].y)q[i].y=0; else q[i].y=lower_bound(b+1,b+m+1,q[i].y)-b; } } void solv(int x,int y,int vt) { int i=0,j=0,pos=0,tmp=0,sum=n; cnt[n]=0,exist[n]=vt; while(p[x][i]!=n+1||p[y][j]!=n+1)//开始对两种颜色一个一个跳 { if(p[x][i+1]<=p[y][j+1])//第一种颜色 { tmp+=(cnt[sum]+cnt[sum]+p[x][i+1]-pos-1)*(p[x][i+1]-pos)/2;//因为sum要++了，所以先计算一下原先的sum值的贡献，当前位置之前到记录的pos都是前一种sum的情况， //每一个位置都可以和之前的所有是sum的位置配对，所以是个排列组合 cnt[sum]+=p[x][i+1]-pos;//这一段更新了原先sum值的个数 pos=p[x][++i],sum++;//pos记录当前sum值的起始位置 if(exist[sum]!=vt)//这种sum还没有存在过，就打个标记开一个这种sum情况的计数数组（其实这就是个清零操作，多组数据嘛，用到再清零） exist[sum]=vt,cnt[sum]=0; } else//是另一种颜色，sum--，其他一样的 { tmp+=(cnt[sum]+cnt[sum]+p[y][j+1]-pos-1)*(p[y][j+1]-pos)/2; cnt[sum]+=p[y][j+1]-pos; pos=p[y][++j],sum--; if(exist[sum]!=vt) exist[sum]=vt,cnt[sum]=0; } } ans[vt]=tmp;//把ans放到对应的位置 } int main() { freopen("interval.in","r",stdin); freopen("interval.out","w",stdout); n=getint(),Q=getint(); for(int i=1;i<=n;++i) a[i]=getint(),b[i]=a[i];; for(int i=1;i<=Q;++i)//这里本来是有记忆化的（相同的询问就可以直接出），所以把询问存下来了，结果搞忘了...... q[i].x=getint(),q[i].y=getint(); lsh(); for(int i=1;i<=Q;++i) solv(q[i].x,q[i].y,i); for(int i=1;i<=Q;++i) cout<<ans[i]<<'\n'; return 0; }本题结。
