UVA 12174 Shuffle

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=2000100;
const int INF=1<<29;

int s,n;
int x[maxn];
int cnt[maxn],m[maxn];

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int T;cin>>T;
    while(T--){
        scanf("%d%d",&s,&n);
        REP(i,1,n) scanf("%d",&x[i]);
        MS0(cnt);MS0(m);
        int k=1;
        int ans=0,tag=1;
        REP(i,1,n){
            cnt[x[i]+k*s]++;
            if(cnt[x[i]+k*s]==2) m[k]++,tag=0;
            if(i%s==0) k++;
        }
        if(tag) ans++;
        //REP(i,0,k) cout<<m[i]<<" ";cout<<endl;
        REP(i,2,s){
            int l=i;
            int k=1;
            bool tag=1;
            while(l-1<=n){
                //cout<<l-1<<" ="<<x[l-1]<<" "<<cnt[x[l-1]+(k-1)*s]<<" "<<x[l-1]+(k-1)*s<<endl;
                cnt[x[l-1]+(k-1)*s]++;
                if(cnt[x[l-1]+(k-1)*s]==2) m[k-1]++;
                cnt[x[l-1]+k*s]--;
                if(cnt[x[l-1]+k*s]==1) m[k]--;
                if(m[k-1]) tag=0;
                k++;
                l+=s;
            }
            //cout<<"i="<<i<<" tag="<<tag<<endl;
            //REP(i,0,k-1) cout<<m[i]<<" ";cout<<endl;
            if(m[k-1]) tag=0;
            if(tag) ans++;
        }
        printf("%d
",ans);
    }
    return 0;
}
/**
先明确一个事实：n个数字被分成k个s段，空间复杂度k*s<=n+s。
然后就可以划窗了。
一开始空间复杂度估计错误，直接去暴力了...why am I so stupid...
*/