この問題は2500点の難易度を持つ競技プログラミングの問題です。

問題概要

二つの異なるアプローチを紹介します。

解法1

まず、各数の出現回数が3の倍数である場合を考えます。区間が有効であるためには、全ての数の出現回数を3で割った余りが0である必要があります。この条件を満たすために、出現回数を3で割った余りの配列をハッシュ化し、以前に同じハッシュ値が出現した位置を探します。これはmapを使用して実装でき、ハッシュテーブルを用いることで線形時間で処理できます。

次に、各数の出現回数がちょうど0回または3回である場合を考えます。ここでは、3より大きく3で割り切れる出現回数を持つ区間を除外する必要があります。各数の出現回数が3以下である左端点は後缀を構成し、右端点が増加するにつれて単調増加します。したがって、リアルタイムでこれを維持し、two-pointers法を適用して除外することができます。

#include<bits/stdc++.h>
using namespace std;
#define pr make_pair
#define fi first
#define se second
#define ins insert
void input(int &x){
    x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
const int MAXN=500000;
int len;
int arr[MAXN+5];
int freq[MAXN+5];
int prev1[MAXN+5],prev2[MAXN+5],prev3[MAXN+5];
const int base1=131,mod1=998244353,base2=13331,mod2=1000000007,hashmod=19260817;
int pow1[MAXN+5],pow2[MAXN+5];
struct hashmap{
    vector<pair<pair<int,int>,int> > buckets[hashmod];
    #define get_bucket buckets[x.fi%hashmod]
    int &operator[](pair<int,int> x){
        for(int i=0;i<get_bucket.size();i++)if(get_bucket[i].fi==x)return get_bucket[i].se;
        get_bucket.push_back(pr(x,0));
        return get_bucket.back().se;
    }
}hash_table;
int hash_val1[MAXN+5],hash_val2[MAXN+5];
int main(){
    input(len);
    for(int i=1;i<=len;i++)input(arr[i]);
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=len;i++)pow1[i]=1ll*pow1[i-1]*base1%mod1,pow2[i]=1ll*pow2[i-1]*base2%mod2;
    int pointer=0;
    hash_table[pr(0,0)]++;
    long long result=0;
    memset(prev1,-1,sizeof(prev1));memset(prev2,-1,sizeof(prev2));memset(prev3,-1,sizeof(prev3));
    for(int i=1;i<=len;i++){
        hash_val1[i]=hash_val1[i-1],hash_val2[i]=hash_val2[i-1];
        (hash_val1[i]-=1ll*freq[arr[i]]*pow1[arr[i]]%mod1)%=mod1,(hash_val2[i]-=1ll*freq[arr[i]]*pow2[arr[i]]%mod2)%=mod2;
        (hash_val1[i]+=1ll*(freq[arr[i]]=(freq[arr[i]]+1)%3)*pow1[arr[i]]%mod1)%=mod1,(hash_val2[i]+=1ll*freq[arr[i]]*pow2[arr[i]]%mod2)%=mod2;
        (hash_val1[i]+=mod1)%=mod1,(hash_val2[i]+=mod2)%=mod2;
        int old_pointer=pointer;
        pointer=max(pointer,prev3[arr[i]]);
        for(int j=old_pointer;j<pointer;j++)hash_table[pr(hash_val1[j],hash_val2[j])]--;
        prev3[arr[i]]=prev2[arr[i]],prev2[arr[i]]=prev1[arr[i]],prev1[arr[i]]=i;
        result+=hash_table[pr(hash_val1[i],hash_val2[i])];
        hash_table[pr(hash_val1[i],hash_val2[i])]++;
    }
    cout<<result;
    return 0;
}

解法2

別の視点から考えてみましょう。左端点を第一軸、右端点を第二軸と見なすと、問題は2次元平面上の点として表現できます。各数の出現回数が0回または3回である条件を満たす区間を、この平面上の有効な点としてマークします。最終的に、n回マークされた点の数を数えれば答えが得られます。

各数に対して、有効な点はO(c)個の部分行列として表現できます。ここでcはその数の出現回数です。しかし、この方法では時間計算量が大きくなりすぎてしまいます。

代わりに、少なくとも一つの数が条件を満たさない点の数を数えることを考えます。これもO(c)個の部分行列として表現できます。このアプローチでは、複数の条件の共通部分を求めるのではなく、単純な和集合を求めるだけなので、オフライン処理とスイープラインアルゴリズムを使用して矩形の面積の和集合を計算できます。

以下に実装例を示します。マークすべき点は以下の4種類です：

• 右端点が左端点より小さい区間
• 現在の数を1つだけ含む区間
• 現在の数を2つだけ含む区間
• 現在の数を4つ以上含む区間

セグメント木は区間への加減算と、全体の0の個数のクエリをサポートする必要があります。ここでは、遅延伝播を用いた効率的な実装を採用しています。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr make_pair
#define fi first
#define se second
const int MAXN=500000;
int size;
vector<int> positions[MAXN+5];
vector<pair<pair<int,int>,pair<int,int> > > rectangles;
struct segment_tree{
    struct node{int left,right,min_val,count,lazy;}tree[MAXN<<2];
    #define l(p) tree[p].left
    #define r(p) tree[p].right
    #define min_val(p) tree[p].min_val
    #define count(p) tree[p].count
    #define lazy(p) tree[p].lazy
    void construct(int l=1,int r=size,int p=1){
        l(p)=l;r(p)=r;min_val(p)=lazy(p)=0;count(p)=r(p)-l(p)+1;
        if(l==r)return;
        int mid=l+r>>1;
        construct(l,mid,p<<1),construct(mid+1,r,p<<1|1);
    }
    void initialize(){construct();}
    void push_up(int p){
        if(min_val(p<<1)==min_val(p<<1|1))min_val(p)=min_val(p<<1),count(p)=count(p<<1)+count(p<<1|1);
        else if(min_val(p<<1)<min_val(p<<1|1))min_val(p)=min_val(p<<1),count(p)=count(p<<1);
        else min_val(p)=min_val(p<<1|1),count(p)=count(p<<1|1);
    }
    void push_down(int p){
        if(lazy(p)){
            min_val(p<<1)+=lazy(p),lazy(p<<1)+=lazy(p);
            min_val(p<<1|1)+=lazy(p),lazy(p<<1|1)+=lazy(p);
            lazy(p)=0;
        }
    }
    void update(int l,int r,int v,int p=1){
        if(l<=l(p)&&r>=r(p))return min_val(p)+=v,lazy(p)+=v,void();
        push_down(p);
        int mid=l(p)+r(p)>>1;
        if(l<=mid)update(l,r,v,p<<1);
        if(r>mid)update(l,r,v,p<<1|1);
        push_up(p);
    }
    int query_zero_count(){return min_val(1)==0?count(1):0;}
}seg_tree;
vector<pair<int,int> > add_events[MAXN+2],remove_events[MAXN+2];
int main(){
    cin>>size;
    for(int i=1;i<=size;i++){
        int val;
        scanf("%d",&val);
        positions[val].pb(i);
    }
    for(int i=1;i<=size;i++)rectangles.pb(pr(pr(i,i),pr(1,i-1)));
    for(int i=1;i<=size;i++){
        vector<int> &vec=positions[i];
        for(int j=0;j<vec.size();j++)rectangles.pb(pr(pr(j?vec[j-1]+1:1,vec[j]),pr(vec[j],j+1==vec.size()?size:vec[j+1]-1)));
        for(int j=0;j+1<vec.size();j++)rectangles.pb(pr(pr(j?vec[j-1]+1:1,vec[j]),pr(vec[j+1],j+2==vec.size()?size:vec[j+2]-1)));
        for(int j=0;j+3<vec.size();j++)rectangles.pb(pr(pr(j?vec[j-1]+1:1,vec[j]),pr(vec[j+3],size)));
    }
    for(int i=0;i<rectangles.size();i++){
        add_events[rectangles[i].fi.fi].pb(rectangles[i].se);
        remove_events[rectangles[i].fi.se+1].pb(rectangles[i].se);
    }
    long long answer=0;
    seg_tree.initialize();
    for(int i=1;i<=size;i++){
        for(int j=0;j<add_events[i].size();j++)seg_tree.update(add_events[i][j].fi,add_events[i][j].se,1);
        for(int j=0;j<remove_events[i].size();j++)seg_tree.update(remove_events[i][j].fi,remove_events[i][j].se,-1);
        answer+=seg_tree.query_zero_count();
    }
    cout<<answer;
    return 0;
}