(T1 text{Part})

题意

定义一个长度为 (k) 的序列 (B) 是好的当且仅当 (forall 1le i<k,B_i=B{i+1}+1)

给出序列 (A)，求最少能把序列 (A) 划分成多少个好的子序列（不要求连续）。

划分指每个元素在这些好的子序列中的一个且仅一个中出现过，值相同但是位置不同的元素也被视为是不同的。

数据范围：(nle {10}^6,1le A_ile {10}^6)

思路

因为 (A_i) 很小，可以用桶维护，从后向前扫一次，如果当前的 (A_i-1) 出现过（指作为某个子序列的末尾），就把 (A_i) 放在这个子序列末尾；如果没有出现过，就另起一个新的子序列，计数 (cnt+1)。

时间复杂度 (O(n))

代码

int n;
int a[maxm],vis[maxm];
int cnt;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=n;i>=1;i--){
        if(!vis[a[i]-1]){
            cnt++;
        }
        else{
            vis[a[i]-1]--;
        }
        vis[a[i]]++;
    }
    printf("%dn",cnt);
    return 0;
}

(T2 text{Seq})

题意

给出一个长度为 (n) 的序列 (A)，求 (A) 有多少个连续子序列的平均值大于等于 (P)。

数据范围：(nle {10}^6)

思路

容易想到前缀和，对于 ([L,R]) 平均值大于等于 (P) 的条件为：

移项可以得到：

因此我们可以维护 (b_i=sum_i-itimes P)，只需要求 (b) 中的顺序对个数，注意这里前缀和可以到 (sum_0)，因此归并排序的区间为 ([0,n])。

代码

int n;
ll ans;
ll a[maxm],b[maxm],p;
inline void msort(int l,int r){
	if(l==r) return;
    int mid=(l+r)>>1;
    msort(l,mid);
    msort(mid+1,r);
    int i=l,j=mid+1,k=i;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            b[k++]=a[i++];
        }
        else{
            b[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid){
        b[k++]=a[i++];
    }
    while(j<=r){
        b[k++]=a[j++];
    }
    for(i=l;i<=r;i++){
        a[i]=b[i];
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    p=read();
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1]-p;
    }
    msort(0,n);
    printf("%lldn",ans);
    return 0;
}

(T3 text{Chess})

题意

有一个 (ntimes n) 的棋盘山有 (k) 个车，每个车都有一个权值 (w_i)。

我们进行如下定义：

一个车能到达它所在的行和列的所有格子（除了他自己所在的格子以外）。

如果所有能到达 ((x,y)) 的车的权值异或和大于 (0)，就称其为被控制的。

在初始局面下，有 (q) 次操作，每次把一个车从一个位置移动到另外一个位置，在每次操作后输出被控制的格子数。

数据范围：(nle {10}^9,kle {10}^5,qle {10}^5,w_ile {10}^9)

思路

考虑到 (ntimes n) 很大，而 (k) 很小，其次“不被控制”的格子所在行和列的异或和是相等的。只需要维护每一行每一列的异或和以及每个值的出现次数。

每次操作时，先删去原有的贡献，再加上目前的贡献。

代码

int n,m,q;
map<int,int> numx,numy,cntx,cnty;
map<pii,int> mp;
ll ans;
inline void update(int x,int y,int w){
    int tmp;
    tmp=numx[x];
    cntx[tmp]--;
    ans=ans-(n-cnty[tmp]);
    numx[x]^=w;
    tmp=numx[x];
    cntx[tmp]++;
    ans=ans+(n-cnty[tmp]);
    tmp=numy[y];
    cnty[tmp]--;
    ans=ans-(n-cntx[tmp]);
    numy[y]^=w;
    tmp=numy[y];
    cnty[tmp]++;
    ans=ans+(n-cntx[tmp]);
}
int main(){
    n=read(),m=read(),q=read();
    cntx[0]=cnty[0]=n;
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),w=read();
        update(x,y,w);
        mp[make_pair(x,y)]=w;
    }
    while(q--){
        int x1=read(),y1=read(),x2=read(),y2=read();
        int tmp=mp[make_pair(x1,y1)];
        update(x1,y1,tmp);
        mp[make_pair(x2,y2)]=tmp;
        update(x2,y2,tmp);
        printf("%lldn",ans);
    }
    return 0;
}

(T4 text{Pref})

题意

如果一个长度为 (k) 的字符串序列 (B) 满足 (forall 1le i<k,B_{i+1}) 是以 (B_i) 开头且以 (B_i) 结尾的，则称 (B) 是好的。

对于一个字符串的序列 (A)，求 (A) 的最长好的子序列的长度。

思路+代码1——哈希

我们只需要顺序枚举每一个字符串，预处理出哈希值以后，对于每一个长度都判断前后缀是否相同且在前面的字符串中出现过（这里用一个 (map) 作桶维护哈希值），之后把整个字符串的哈希值放入桶中。

考虑到总字符串长度为 (le 2times{10}^6)，显然操作是 (O(n)) 的。

int n;
char s[maxn];
ull power[maxn],h[maxn];
int dp[maxn];
map<ull,int> mp;
int ans,maxx;
int main(){
    power[0]=1;
    for(int i=1;i<=maxn;i++){
        power[i]=power[i-1]*base1;
    }
    n=read();
    for(int i=1;i<=n;i++){
        maxx=0;
        scanf("%s",s+1);
        int len=strlen(s+1);
        ull preh=0,sufh=0;
        for(int j=1;j<=len;j++){
            preh=preh*base1+s[j];
            sufh=sufh+s[len-j+1]*power[j-1];
            if(preh==sufh){
                maxx=max(maxx,mp[preh]);
            }
        }
        mp[preh]=max(mp[preh],maxx+1);
        ans=max(ans,maxx+1);
    }
    printf("%dn",ans);
    return 0;
}