\(T1\ \text{Part}\)

meaning of the title

Defining a sequence \ (B \) with a length of \ (k \) is good if and only if \ (\ forall 1 \ le I < k, b_i = B {I + 1} + 1 \)

Give the sequence \ (A \), and find out how many good subsequences the sequence \ (A \) can be divided into (continuous is not required).

Partition means that each element has appeared in one and only one of these good subsequences. Elements with the same value but different positions are also considered to be different.

Data range: \ (n\le {10}^6,1\le A_i\le {10}^6 \)

thinking

Because \ (A_i \) is very small, it can be maintained with a bucket. Sweep it from the back to the front. If the current \ (A_i-1 \) has appeared (referring to the end of a subsequence), put \ (A_i \) at the end of the subsequence; If it does not appear, a new subsequence will be created, counting \ (cnt+1 \).

Time complexity \ (O(n) \)

code

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("%d\n",cnt);
    return 0;
}

\(T2\ \text{Seq}\)

meaning of the title

Give A sequence \ (A \) with A length of \ (n \), and find how many consecutive subsequences of \ (A \) have an average value greater than or equal to \ (P \).

Data range: \ (n\le {10}^6 \)

thinking

It is easy to think of prefix and. For the average value of \ ([L,R] \) greater than or equal to \ (P \), the conditions are:

By shifting items, we can get:

Therefore, we can maintain \ (b_i=sum_i-i\times P \) and only require the number of sequential pairs in \ (B \). Note that the prefix and can be to \ (sum_0 \), so the interval of merging and sorting is \ ([0,n] \).

code

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("%lld\n",ans);
    return 0;
}

\(T3\ \text{Chess}\)

meaning of the title

There is a \ (n\times n \) chessboard mountain with \ (k \) cars, and each car has a weight \ (w_i \).

We define it as follows:

A car can reach all the grids of its row and column (except its own grid).

If the exclusive or sum of weights of all vehicles that can reach \ ((x,y) \) is greater than \ (0 \), it is called controlled.

In the initial situation, there are \ (q \) operations, moving a car from one position to another each time, and outputting the number of controlled grids after each operation.

Data range: \ (n\le {10}^9,k\le {10}^5,q\le {10}^5,w_i\le {10}^9 \)

thinking

Considering that \ (n\times n \) is large and \ (k \) is small, the XOR sum of the row and column of the "uncontrolled" grid is equal. You only need to maintain the XOR sum of each row and column and the number of occurrences of each value.

In each operation, delete the original contribution and add the current contribution.

code

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("%lld\n",ans);
    }
    return 0;
}

\(T4\ \text{Pref}\)

meaning of the title

If a string sequence \ (B \) with length \ (k \) satisfies that \ (\ forall 1 \ le I < k, B {I + 1} \) starts with \ (B_i \) and ends with \ (B_i \), then \ (B \) is good.

For the sequence of A string \ (A \), find the length of the longest and best subsequence of \ (A \).

Idea + code 1 - hash

We only need to enumerate each string in sequence. After preprocessing the hash value, judge whether the pre suffix is the same for each length and has appeared in the previous string (here, a \ (map \) is used as a bucket to maintain the hash value), and then put the hash value of the whole string into the bucket.

Considering that the total string length is \ (\ le 2\times{10}^6 \), it is obvious that the operation is \ (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("%d\n",ans);
    return 0;
}