题解 P4065 【[JXOI2017]颜色】

· · 题解

提供一个不用自己写数据结构过此题的题解。。。

合法的区间就是包含所有的在区间内出现过得颜色。。

这种题有一种神奇的hash做法。。。

我们给所有颜色相同的位置赋一个值，使得同色的位置的值加起来等于0

然后统计答案的方法比较显然，维护一个前缀和，然后两个前缀和相同的位置就可以搞出一个合法区间。。

至于这种做法的正确性。。。感觉记得某大佬曾经证过。。。但是窝不会。。。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<vector>
#include<map>
#define LL long long
using namespace std;
const int N=3e5+10;
const LL mod=1e12;
int n;
int a[N];
map<LL,LL> mp;
LL f[N];
vector<int> ve[N];
int main(){
    int T;scanf("%d",&T);
    LL re=0,x,op,ans=0;
    while(T--){
        scanf("%d",&n);ans=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            ve[a[i]].push_back(i);
        }
        for(int i=1;i<=n;++i){
            if(ve[i].size()==0) continue;
            if(ve[i].size()==1) f[ve[i][0]]=0;
            re=0;
            for(int j=0;j<ve[i].size()-1;++j){
                x=rand()*rand()%mod*rand()%mod*rand()%mod;
                op=rand()&1;if(op) x=-x;
                f[ve[i][j]]=x;re+=x;
            }
            f[ve[i][ve[i].size()-1]]=-re;
        }
        mp.clear();re=0;mp[0]=1;
        for(int i=1;i<=n;++i){
            re+=f[i];
            ans+=mp[re];
            ++mp[re];
        }
        printf("%lld\n",ans);
        for(int i=1;i<=n;++i) ve[i].clear();
    }
    return 0;
}