题面

这里

题解

下次再打错字母我剁手……

预计得分\(100+45+100=245\)，实际得分\(100+45+56=201\)

\(T3\)打错了一个字母……

\(T1\)

先说明一下，\(S\)和\(T\)的下标都是从\(0\)开始，并且所有值都默认对\(n\)取模

我们发现，如果以\(p\)为开头的\(S\)中的第\(p+i\)位和\(T\)中的第\(i\)位相同的话话，可以写成这个形式\[[(a\times (p+i)+b)\mod n\geq c]=T_i\]

然后化一下式子变成\[[(a\times i+b+a\times p)\mod n\geq c]=T_i\]

考虑左边的不等号左边的式子\(a\times i+b+a\times p\)，因为\(a\times i+b\)和\(a\times p\)都小于\(n\)，所以这两个值加起来模\(n\)大于\(c\)的话，说明它们的值域为\([c,n-1]\)或\([c+n,2n-1]\)，那么\(a\times i+b\)的值域就是\([c-a\times p,n-1-a\times p]\)或者\([c+n-a\times p,2n-1-a\times p]\)

记\(v_i=a\times i+b\)，那么对于\(i\in[1,m]\)，\(v_i\)是定值

对于每一次询问的\(p\)，如果一个\(v_i\)的值落在上述区间内，说明\(S_{p+i}\)的值为\(1\)，此时如果\(T_i\)的值也为\(1\)则它们相等，否则不等

那么，总共的不等的字符个数就是值在区间内且\(T_i\)为\(0\)的以及值不在区间内切\(T_i\)为\(1\)的

那么对于值域开一个动态开点线段树，记录一下区间内\(T_i\)为\(0\)和\(T_i\)为\(1\)的数的个数，然后直接查询就行了

复杂度\(O(m\log n)\)

//minamoto
#include<bits/stdc++.h>
#define R register
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0'){(ch=='-')&&(f=-1);if(ch==EOF)return EOF;}
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
void read(char *s){
    R int len=0;R char ch;while((ch=getc())!='0'&&ch!='1');
    while(s[len++]=ch,((ch=getc())=='0'||ch=='1'));s[len]=0;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,M=N<<5;
int sum[M][2],ls[M],rs[M],v[N],s[N];char t[N];
int n,rt,a,b,c,m,tot,num0,num1,ql,qr,q,op,x;
void ins(int &p,int l,int r,int x,int v){
    if(!p)p=++tot;++sum[p][v];if(l==r)return;
    int mid=(l+r)>>1;
    x<=mid?ins(ls[p],l,mid,x,v):ins(rs[p],mid+1,r,x,v);
}
void upd(int &p,int l,int r,int x,int v){
    if(!p)p=++tot;--sum[p][v],++sum[p][v^1];if(l==r)return;
    int mid=(l+r)>>1;
    x<=mid?upd(ls[p],l,mid,x,v):upd(rs[p],mid+1,r,x,v);
}
void query(int p,int l,int r){
    if(!p||ql<=l&&qr>=r)return num0+=sum[p][0],num1+=sum[p][1],void();
    int mid=(l+r)>>1;
    if(ql<=mid)query(ls[p],l,mid);
    if(qr>mid)query(rs[p],mid+1,r);
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    n=read(),a=read(),b=read(),c=read(),m=read();
    read(t);fp(i,0,m-1)s[i]=t[i]-'0',v[i]=(1ll*a*i+b)%n,ins(rt,0,n-1,v[i],s[i]);
    q=read();
    while(q--){
        op=read(),x=read();
        if(op&2)upd(rt,0,n-1,v[x],s[x]),s[x]^=1;
        else{
            x=1ll*a*x%n,ql=c-x,qr=n-1-x,num0=num1=0;
            if(ql<=qr&&qr>=0&&ql<n)query(rt,0,n-1);
            ql+=n,qr+=n;
            if(ql<=qr&&qr>=0&&ql<n)query(rt,0,n-1);
            print(sum[rt][1]-num1+num0);
        }
    }
    return Ot(),0;
}

\(T2\)

一下记\(n\)表示操作次数，\(m\)表示模数

我们建两个栈，如果是往前插入，把它加入第一个栈中，往后加入则加入第二个栈中。每次加入一个物品之后，做一遍背包，并将这个背包的值记录下来。每一次加入物品的复杂度都是\(O(m)\)

对于删除操作，如果栈非空直接\(--top\)就行了，否则的话，我们把两个栈给暴力重构，把非空的那个栈取出一半元素给另一个栈，每次重构的复杂度为\(O(nm)\)。因为每重构一次栈的大小就会减少一半，所以每个点最多参与\(O(\log n)\)次重构，所以这一部分复杂度为\(O(nm\log n)\)。（不过这个上界很松，我还没想到有什么数据可以卡到上界，我想到的数据这一部分的复杂度都是\(O(nm)\)的）

然后是查询操作。我们需要将两个栈栈顶的\(dp\)数组合并，朴素地合并的话是\(O(m^2)\)的，不够优秀。我们考虑枚举其中一个栈，设当前特征值为\(w\)，当前特征值下的最大战斗力为\(v\)，令\(ql=(l-w+P)\%P,qr=(r-w+P)\%P\)，那么要令特征值落在\([l,r]\)的范围内，另一个栈里取出的元素的特征值必须在\([ql,qr]\)的范围内（如果\(qr<ql\)则是在\([0,qr]\)或\([ql,P-1]\)的范围内）。我们对另一个栈预处理一下\(ST\)表，就可以每一次\(O(1)\)查询了，这一部分的复杂度是\(O(nm\log m)\)

于是总的复杂度是\(O(nm\log n)\)

//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inf 1e18
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0'){(ch=='-')&&(f=-1);if(ch==EOF)return EOF;}
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R ll x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=50005,M=505,L=11;
int n,P,Log[M];ll ans,rmq[M][L];
struct node{
    int top,w[N],v[N];ll f[N][M];
    node(){memset(f[0],0xef,sizeof(f[0]));f[0][0]=0;}
    void push(int W,int V){
        ++top,w[top]=W,v[top]=V;
        fp(i,0,P-1)f[top][(i+W)%P]=max(f[top-1][(i+W)%P],f[top-1][i]+V);
    }
}st[2];
void del(int p){
    if(!st[p].top){
        int q=p^1,tot=st[q].top,mid=(tot+1)>>1;if(tot==1)return --st[q].top,void();
        fd(i,mid,2)st[p].push(st[q].w[i],st[q].v[i]);
        st[q].top=0;fp(i,mid+1,tot)st[q].push(st[q].w[i],st[q].v[i]);
    }else if(--st[p].top==0){
        int q=p^1,tot=st[q].top,mid=(tot+1)>>1;
        fd(i,mid,1)st[p].push(st[q].w[i],st[q].v[i]);
        st[q].top=0;fp(i,mid+1,tot)st[q].push(st[q].w[i],st[q].v[i]);
    }
}
void init(){
    fp(i,0,P-1)rmq[i][0]=st[1].f[st[1].top][i];
    for(R int j=1;(1<<j)<=P;++j)for(R int i=0;i+(1<<j)-1<P;++i)
        rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
    fp(i,2,P)Log[i]=Log[i>>1]+1;
}
inline ll Max(R int l,R int r){int k=Log[r-l+1];return max(rmq[l][k],rmq[r-(1<<k)+1][k]);}
ll query(R int l,R int r,ll ans=-1){
    int k=st[0].top;
    fp(i,0,P-1)if(st[0].f[k][i]>=0){
        int ql=(l-i+P)%P,qr=(r-i+P)%P;
        cmax(ans,st[0].f[k][i]+(ql<=qr?Max(ql,qr):max(Max(0,qr),Max(ql,P-1))));
    }return ans;
}
int x,y;
int main(){
//  freopen("testdata,in","r",stdin);
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    n=read(),P=read();
    fp(i,1,n){
        R char ch,dh;while((ch=getc())>'Z'||ch<'A');dh=getc();
        if(ch!='D')x=read()^ans,y=read()^ans;
        if(ch=='I')st[dh=='G'].push(x,y);
        if(ch=='D')del(dh=='G');
        if(ch=='Q')init(),print(ans=query(x,y));
    }
    return Ot(),0;
}

\(T3\)

设\(1\)号点为\(rt\)，我们分两种情况考虑，一种是\(a_i\)在\(rt\)的子树内，一种是\(a_i\)在\(rt\)的子树外，并记\(res\)表示没有被\(1\)号点占领的点的总数

首先不难看出，如果\(a_i\)和\(rt\)中间隔着\(d\)个点，那么\(a_i\)能占领的是其中的\(\left\lfloor\frac{d}{2}\right\rfloor\)个点

先考虑所有在\(rt\)的子树内的点，对于一个点\(a_i\)，我们倍增让它跳到它能占领的深度最小的点\(p_i\)，那么\(p_i\)以及它的子树都会变得不可选，于是\(res+=size_{p_i}\)

然而会有一个问题，比方说\(p_j\)在\(p_i\)的子树中，然而按上面的方法的话\(p_j\)的子树被统计了两次，显然不行

那么我们把所有的\(p_i\)按照欧拉序排序，那么\(p_i\)的子树中的点一定在\(p_i\)之后的一段连续的区间里，我们用一个指针扫一下，只加上\(p_i\)的贡献，然后令\(i\)跳过这段区间就行了

接下来的问题就是\(a_i\)在\(rt\)子树之外的情况。此时如果\(p_i\)不在\(rt\)到根节点的路径上，那么被删除的依然是一棵子树，按照\(a_i\)在\(rt\)子树内的方法做就行了

如果\(p_i\)在\(rt\)到根节点的路径上，我们记\(v\)表示\(rt\)能占领的最后一个点，也就是\(p_i\)到\(rt\)的路径上的第一个点，那么\(res+=n-size_v\)。并且我们发现，我们只要记录下深度最深的一个\(v\)，并计算它的贡献就行了

顺带一提，对于那些\(p_i\)不在\(rt\)到根节点路径上的点，显然只有当\(dep_{LCA(rt,a_i)}\geq dep_v\)时才会有贡献

于是总的复杂度为\(O(k\log n)\)

//minamoto
#include<bits/stdc++.h>
#define R register
#define inf 0x3f3f3f3f
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0'){(ch=='-')&&(f=-1);if(ch==EOF)return EOF;}
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=5e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int dfn[N],Top[N],sz[N],fa[N],ga[N][25],st[N],p[N],q[N],dq[N],dep[N],son[N],ls[N],rs[N];
int n,m,u,v,d,top,rt,x,t,cnt,res,k;
inline void init(R int u){ga[u][0]=fa[u];for(R int i=1;i<=19&&ga[u][i-1];++i)ga[u][i]=ga[ga[u][i-1]][i-1];} 
void dfs1(int u){
    sz[u]=1,dep[u]=dep[fa[u]]+1,init(u);
    go(u)if(v!=fa[u]){
        fa[v]=u,dfs1(v),sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    Top[u]=t,ls[u]=++cnt;
    if(!son[u])return rs[u]=cnt,void();
    dfs2(son[u],t);
    go(u)if(!Top[v])dfs2(v,v);
    rs[u]=cnt;
}
int LCA(int u,int v){
    while(Top[u]!=Top[v]){
        if(dep[Top[u]]<dep[Top[v]])swap(u,v);
        u=fa[Top[u]];
    }return dep[u]<dep[v]?u:v;
}
inline int dis(R int u,R int v){return dep[u]+dep[v]-(dep[LCA(u,v)]<<1)-1;}
inline int Kth(int u,int k){if(!k)return u;fd(i,19,0)if(k>>i&1)u=ga[u][i];return u;}
inline bool cmp(const R int &x,const R int &y){return ls[x]<ls[y];}
void solve1(){
    fp(i,1,top){
        d=dep[st[i]]-dep[rt]-1,d-=(d+1)>>1;
        st[i]=Kth(st[i],d);
    }
    sort(st+1,st+1+top,cmp);
    for(R int i=1,j=1;i<=top;i=j){
        while(j<=top&&ls[st[j]]>=ls[st[i]]&&ls[st[j]]<=rs[st[i]])++j;
        res+=sz[st[i]];
    }
}
void solve2(){
    int mx=1,s=1,h;
    fp(i,1,t){
        int lca=LCA(rt,q[i]),c=dep[rt]+dep[q[i]]-(dep[lca]<<1)-1,d=c-((c+1)>>1),f;
        dq[i]=dep[lca];
        if(d<dep[q[i]]-dep[lca])q[i]=Kth(q[i],d);
        else d=c-d,f=Kth(rt,d),cmax(mx,dep[f])?s=f:0;
    }
    res+=n-sz[s],h=t,t=0;
    fp(i,1,h)if(dq[i]>=mx)q[++t]=q[i];
    sort(q+1,q+1+t,cmp);
    for(R int i=1,j=1;i<=t;i=j){
        while(j<=t&&ls[q[j]]>=ls[q[i]]&&ls[q[j]]<=rs[q[i]])++j;
        res+=sz[q[i]];
    }
}
int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read(),m=read();
    fp(i,1,n-1)u=read(),v=read(),add(u,v),add(v,u);
    dfs1(1),dfs2(1,1);
    while(m--){
        k=read(),res=0,top=0,t=0,rt=read();
        fp(i,2,k){
            x=read();
            (ls[x]<ls[rt]||ls[x]>rs[rt])?q[++t]=x:st[++top]=x;
        }
        solve1(),solve2();
        print(n-res);
    }
    return Ot(),0;
}

ZJOI2019 模拟赛 三by Lowest（密码我名字全拼）

原文：https://www.cnblogs.com/bztMinamoto/p/10389039.html