CF题目泛做1

 x 是看题解的。

[] CF1055E

题意：给定 $n$ 个点，以及 $m$ 条线段，选择 $s$ 条线段，使得至少被一个线段覆盖的点的坐标从小到大排序后，第 $k$ 大最小，没有则输出 $-1$ 。

二分答案 $k$ ，则现在问题变为了选择 $k$ 个线段使得至少覆盖 $p$ 个点。

按照 $r$ 排序后考虑 $dp$，设 $f_i$ 表示选择 $i$ 的最多点数。

由于直接转移是 $O(m^3)$ 通不过本题，则对于相交与不相交建立线段树维护即可。

时间复杂度 $O(m^2log^2n)$ 。

貌似可以对于点 $dp$ ，维护每个点最右连续 $1$ 位置。$O(1)$ 转移即可，时间复杂度 $O(m^2log n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1501;
struct Segment{
    int Maxn[MAXN<<2],inf;
    void clear(){memset(Maxn,-127/3,sizeof(Maxn));inf=Maxn[0];return;}
    void Modify(int k,int l,int r,int ps,int w){
        if(l==r){Maxn[k]=w;return;}
        int mid=(l+r)>>1; if(ps<=mid) Modify(k<<1,l,mid,ps,w); if(mid<ps) Modify(k<<1|1,mid+1,r,ps,w);
        Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]); return;
    }
    int Query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return Maxn[k];
        int res=inf,mid=(l+r)>>1; if(x<=mid) res=max(res,Query(k<<1,l,mid,x,y)); if(mid<y) res=max(res,Query(k<<1|1,mid+1,r,x,y));
        return res;
    }
}S[MAXN];
int N,M,K,kth,A[MAXN],tmp[MAXN],cnt,SS[MAXN];
struct Node{int l,r,len;} F[MAXN],G[MAXN];
int f[MAXN][MAXN],pre[MAXN],Maxn[MAXN][MAXN];
bool cmp(Node x1,Node x2){return x1.len<x2.len;}
bool cmp1(Node x1,Node x2){return x1.r<x2.r;}
bool check(int xx){
    for(int i=1;i<=N;i++) SS[i]=SS[i-1]+(A[i]<=xx);
    for(int i=0;i<=K;i++) S[i].clear();
    memset(f,-127/3,sizeof(f)); memset(Maxn,-127/3,sizeof(Maxn));f[0][0]=0; S[0].Modify(1,0,cnt,0,0);
    for(int i=0;i<=cnt;i++) Maxn[0][i]=0;
    int Max=0;
    for(int i=1;i<=K;i++){
        for(int j=1;j<=cnt;j++){
            f[i][j]=max(f[i][j],Maxn[i-1][pre[j]]+SS[G[j].r]-SS[G[j].l-1]);
            if(pre[j]+1<=j-1){    
                int W=S[i-1].Query(1,0,cnt,pre[j]+1,j-1)+SS[G[j].r];
                f[i][j]=max(f[i][j],W);    
            }
            Maxn[i][j]=max(f[i][j],Maxn[i][j-1]);
            Max=max(Max,f[i][j]);
            S[i].Modify(1,0,cnt,j,f[i][j]-SS[G[j].r]);
        }
    }
    return Max>=kth;
}
int main(){
    //freopen("A.in","r",stdin);
    N=read(),M=read(),K=read(),kth=read();
    for(int i=1;i<=N;i++) A[i]=tmp[i]=read(); sort(tmp+1,tmp+N+1);
    int E=unique(tmp+1,tmp+N+1)-tmp-1;
    for(int i=1;i<=N;i++) A[i]=lower_bound(tmp+1,tmp+E+1,A[i])-tmp;
    for(int i=1;i<=M;i++) F[i].l=read(),F[i].r=read(),F[i].len=F[i].r-F[i].l+1; sort(F+1,F+M+1,cmp);
    for(int i=1;i<=M;i++){
        bool ff=1; for(int j=i+1;j<=M;j++) if(F[j].l<=F[i].l&&F[i].r<=F[j].r) {ff=0;break;}
        if(ff) G[++cnt]=F[i];
    }sort(G+1,G+cnt+1,cmp1); int l=1,r=E,res=-1;
    for(int i=1;i<=cnt;i++) for(int j=0;j<=i-1;j++) if(G[j].r<G[i].l) pre[i]=j;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }if(res==-1) printf("-1
"); else printf("%d
",tmp[res]);
    return 0;
}/*
4 3 2 2
3 1 3 2
1 2
2 3
4 4
*/
View Code

[] CF1428F

题意：给定一个 $0/1$ 字符串，设 $f_{i,j}$ 表示从 $i$ 到 $j$ 最长的全部为 $1$ 的子串的长度，求 $sum_{i=1}^n sum_{j=i}^n f_{i,j}$ 。 

枚举 $r$ 考虑如何计算答案。我们会发现会增加贡献的只有段是递增的。

即维护一个递减的单调栈，答案是简单计算可得。时间复杂度 $O(n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<stack>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=5e5+11;
char str[MAXN]; int tot,N,A[MAXN],Ans[MAXN],c0,c1,gg;
pii sta[MAXN];//l_i,x_i+l_i
signed main(){
    //freopen("B.in","r",stdin);
    N=read(); scanf("%s",str+1); for(int i=1;i<=N;i++) A[i]=str[i]-'0';
    for(int i=1;i<=N;i++){
        if(A[i-1]==1&&A[i]==0){c0=c1=0;}
        if(A[i]==0){c0++;Ans[i]=Ans[i-1];continue;}
        if(A[i-1]!=A[i]){
            c1++;
            int fir=0,sec=0;
            while(tot&&sta[tot].fi<c1) fir+=sta[tot].fi,sec+=sta[tot].se,gg-=sta[tot].se*sta[tot].se,tot--;
            sta[++tot]=mp(c1,c1+c0+sec);
            gg+=c1*(c1+c0+sec);
            int end=sta[1].fi; int res=0;
            res+=((1+end)*end)/2;
            res+=gg;
            //for(int j=1;j<=tot;j++) res+=sta[j].se*sta[j].fi;
            res-=sta[1].fi*sta[1].fi;
            Ans[i]=res;
        }else{
            //cerr<<"c0:"<<c0<<endl;
            int fir=0,sec=0;sec+=sta[tot].se-c1-c0;
            gg-=sta[tot].fi*sta[tot].se;tot--;c1++;
            while(tot&&sta[tot].fi<c1) fir+=sta[tot].fi,sec+=sta[tot].se,gg-=sta[tot].fi*sta[tot].se,tot--;
            sta[++tot]=mp(c1,c1+c0+sec);
            gg+=c1*(c0+c1+sec);
            int end=sta[1].fi; int res=0;
            res+=((1+end)*end)/2;res+=gg;
            //for(int j=1;j<=tot;j++) res+=sta[j].se*sta[j].fi;
            res-=sta[1].fi*sta[1].fi;
            Ans[i]=res;
        }
        /*printf("==============
");
        int sum=0; for(int j=1;j<=tot;j++) sum+=sta[j].se;
        cerr<<i<<" "<<sum<<endl;
        for(int j=1;j<=tot;j++) printf("(%lld,%lld) ",sta[j].fi,sta[j].se);printf("
");
        printf("==============
");*/
    } int res=0;
    //for(int i=1;i<=N;i++) printf("%lld ",Ans[i]);printf("
");
    for(int i=1;i<=N;i++) res+=Ans[i];
    printf("%lld
",res);
    return 0;
}
/*
100
01101 10011 01111 1001110000110010010000111111001100001011101101000001011001101100111011111100111101110
*/
View Code

[x] CF1389F

题意：有 $n$ 条线段，每个线段是黑白两种颜色之一，求在 $n$ 条线段中选择最多线段使得任意白色线段与黑色线段无交。

没看出是暴力 $dp$ 。考虑设 $f_{i,j}$ 表示前 $i$ 段，其中最后一个是白色，且 $r_{max}$ 为 $j$ 的最大段数，同理得到 $g$ 表示黑色。

所有线段按 $r$ 排序后考虑第 $i$ 条线段是白色的情况。

1) 若不选，则 $g_{i,j}=g_{i-1,j}$ , $f_{i,j}=f_{i-1,j}$ 。

2) 若选，则 $g_{i,j}=g_{i-1,j}$ , $f_{i,r_i}=max_{0leq k<l_i}{g_{i-1,k}+count(k,i)}$ ,$count(i,j)$ 表示线段完全包含在 $[i,j]$ 的个数。

而对于 $count$ ，因为 $r$ 是不断递增的，所以动态累加即可。

可以发现每次操作最多会改变一个 $dp$ 值，即线段树维护求前缀最大值，区间加即可。

时间复杂度 $O(nlog n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=4e5+11;
int N,tmp[MAXN],M,Maxn; struct Node{int l,r,col;}E[MAXN];
bool cmp(Node x1,Node x2){return x1.r<x2.r;}
struct Segment{
    int tag[MAXN<<2],Maxn[MAXN<<2];
    void Init(){memset(Maxn,-127/3,sizeof(Maxn));return;}
    void pushdown(int k){
        if(!tag[k]) return;
        Maxn[k<<1]+=tag[k],Maxn[k<<1|1]+=tag[k];
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
        tag[k]=0; return;
    }
    void Modify(int k,int l,int r,int ps,int w){
        if(l==r){Maxn[k]=w; return;} pushdown(k);
        int mid=(l+r)>>1; if(ps<=mid) Modify(k<<1,l,mid,ps,w); else Modify(k<<1|1,mid+1,r,ps,w);
        Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]); return;
    }
    void Add(int k,int l,int r,int x,int y,int w){
        if(x<=l&&r<=y){tag[k]+=w;Maxn[k]+=w; return;} pushdown(k);
        int mid=(l+r)>>1; if(x<=mid) Add(k<<1,l,mid,x,y,w); if(mid<y) Add(k<<1|1,mid+1,r,x,y,w);
        Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]); return;
    }
    int Query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return Maxn[k]; pushdown(k);
        int res=INT_MIN,mid=(l+r)>>1;
        if(x<=mid) res=max(res,Query(k<<1,l,mid,x,y));
        if(mid<y) res=max(res,Query(k<<1|1,mid+1,r,x,y));
        Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]); return res;
    }
}f[2];
int Hash(int x){return lower_bound(tmp+1,tmp+M+1,x)-tmp;}
int main(){
    //freopen("2.in","r",stdin);
    N=read()+1-1; for(int i=1;i<=N;i++) E[i].l=read(),E[i].r=read(),E[i].col=read()-1,tmp[++tmp[0]]=E[i].l,tmp[++tmp[0]]=E[i].r;
    sort(tmp+1,tmp+tmp[0]+1); M=unique(tmp+1,tmp+tmp[0]+1)-tmp-1; for(int i=1;i<=N;i++) E[i].l=Hash(E[i].l),E[i].r=Hash(E[i].r);
    f[0].Init(),f[1].Init(); f[0].Modify(1,0,M,0,0),f[1].Modify(1,0,M,0,0); sort(E+1,E+N+1,cmp);
    //for(int i=1;i<=N;i++) printf("%d %d %d
",E[i].l,E[i].r,E[i].col);
    for(int i=1;i<=N;i++){
        //don't  can not move
        int W=f[E[i].col^1].Query(1,0,M,0,E[i].l-1)+1,cur=f[E[i].col].Query(1,0,M,E[i].r,E[i].r);
        //cerr<<"W:"<<W<<" cur:"<<cur<<endl;
        if(W>cur) f[E[i].col].Modify(1,0,M,E[i].r,W);
        //update 
        //cerr<<"i:"<<i<<" r:"<<E[i].l-1<<endl;
        f[E[i].col^1].Add(1,0,M,0,E[i].l-1,1);
    } Maxn=max(f[0].Query(1,0,M,0,M),f[1].Query(1,0,M,0,M));
    printf("%d
",Maxn); return 0;
}/*
5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
*/
View Code

 [] CF771D

题意：输入一个字符串，你可以进行一些操作，每次操作可以交换两个相邻的字符。问至少进行几次操作，才能使这个字符串不包含子串 $VK$ 。 

因为其他字符（除 $V,K$ ） 是一样的统一起来看。 由于字符串交换变为另一个字符串答案是其逆序对个数，且每相同字符相对顺序不变。

那么对于此题我们只需要知道前面有几个 $V$，几个 $K$ ，几个其余字符其实位置我们就知道了。

设 $f_{i,j,k,0/1/2}$ 表示当前有 $i$ 个 $V$ ，$j$ 个 $K$ , $k$ 个其余，且当前位置填的啥时 $j<i且ps_j<ps_i$ 的答案。预处理后直接转移即可。

答案即为 $dfrac{n imes (n+1)}{2}-f$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=76;
int N,f[MAXN][MAXN][MAXN][5],A[MAXN],Num[MAXN][4],Ps[MAXN][4],c0,c1,c2; char str[MAXN];
int main(){
    //freopen("1.in","r",stdin);
    N=read(); scanf("%s",str+1);
    for(int i=1;i<=N;i++){
        if(str[i]=='V') A[i]=0,Ps[++c0][0]=i;
        else if(str[i]=='K') A[i]=1,Ps[++c1][1]=i;
        else A[i]=2,Ps[++c2][2]=i;
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<=2;j++) Num[i][j]=Num[i-1][j];
        Num[i][A[i]]++;
    }
    //cerr<<c0<<" "<<c1<<" "<<c2<<endl;
    memset(f,-127/3,sizeof(f)); f[0][0][0][2]=0;
    for(int i=0;i<=c0;i++){
        for(int j=0;j<=c1;j++){
            for(int k=0;k<=c2;k++){
                for(int p1=0;p1<=2;p1++){
                    //printf("f(%d,%d,%d,%d):%d
",i,j,k,p1,f[i][j][k][p1]);
                    f[i+1][j][k][0]=max(f[i+1][j][k][0],f[i][j][k][p1]+ i + min(Num[Ps[i+1][0]][1],j) + min(Num[Ps[i+1][0]][2],k) );
                    if(p1!=0) f[i][j+1][k][1]=max(f[i][j+1][k][1],f[i][j][k][p1]+ j + min(Num[Ps[j+1][1]][0],i) + min(Num[Ps[j+1][1]][2],k) );
                    f[i][j][k+1][2]=max(f[i][j][k+1][2],f[i][j][k][p1]+ k + min(Num[Ps[k+1][2]][0],i) + min(Num[Ps[k+1][2]][1],j) );
                }
            }
        }
    }
    int Minn=max(max(f[c0][c1][c2][0],f[c0][c1][c2][1]),f[c0][c1][c2][2]);
    printf("%d
",(N*(N-1))/2-Minn); return 0;
}
View Code

[] CF1093F

题意：一个长度 $n$ 的序列，每个元素有 $1sim m$ 的颜色，有些位置的颜色给定，其它的在 $1sim m$ 中任取，求将其染色的方案数，使得相邻 $l$ 个元素颜色不全相同。 

设 $f_{i,j}$ 表示当前在 $i$，其中第 $i$ 个选 $j$ 的方案数，设 $S_i=sum f_{i,x}$ 。

则当 $[i-len+1,i-1]$ 不能填 $j$ 时 , $f_{i,j}=S_{i-1}$ 。

否则，$f_{i,j}=S_{i-1}-S_{i-len}+f_{i-len,j}$ 。

时间复杂度 $O(nk)$ ，实际上本题可以做到 $O(n)$ ，详情见 link 。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define int long long
#define mod 998244353
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e5+11;
const int MAXK=101;
int f[MAXN][MAXK],N,K,len,A[MAXN],S[MAXN],cnt[MAXN],pre[MAXN][MAXK];
signed main(){
    N=read(),K=read(),len=read();
    for(int i=1;i<=N;i++) A[i]=read();
    for(int i=1;i<=N;i++){
        cnt[A[i]]++;
        if(i-len>=1) cnt[A[i-len]]--;
        int ss=0,ps=-1;
        for(int j=1;j<=K;j++) if(cnt[j]){ss++;ps=j;}
        if(!ss){
            for(int j=1;j<=K;j++) pre[i][j]=1;
            continue;
        }
        if(ss==1){
            pre[i][ps]=1;continue;
        }
    }
    S[0]=1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=K;j++){
            if(A[i]!=-1&&A[i]!=j) continue;
            f[i][j]=S[i-1];  bool ff=1;
            if(i-len+1>=1){
                if(pre[i][j]){    
                    if(ff) f[i][j]=(f[i][j]-S[i-len]+f[i-len][j]+mod)%mod;    
                }
            }
            S[i]+=f[i][j],S[i]%=mod;
        }
    }int Ans=0;
    for(int i=1;i<=K;i++) Ans+=f[N][i],Ans%=mod;
    printf("%lld
",Ans); return 0;
}/*
5 2 3
1 -1 1 -1 2
*/
View Code

[] CF627D

题意：给出一棵无根树，每个节点有一个权值。你可以指定树根和访问顺序，使得前 $k$ 个结点的 $dfs$ 序的最小值最大，求出这个值 。

二分答案 $Lim$ ，则问题转换成是否存在 $dfs$ 序使得前 $k$ 个点都为 $1$ 。

则枚举起始点 $dp$ 即可，可以发现 $dp$ 可以换根则再写个换根 $dp$ 即可。

过题才发现大家的做法都是枚举每个点子树中的一个点为起始点，则答案为 $all+Maxn_1+Maxn_2$ ，$all$ 为子树填满， $Maxn_1$ 为不满的最大值， $Maxn_2$ 为次大值。

由于除原树根节点为以其他点为根都可以将他到根的那个子树作为满的才满足题意，因为若不满足则肯定可以追溯到该点到根的链上的另一点，该点满足子树外的满，或是走不下去。那时这种情况会被统计。

时间复杂度 $O(nlog n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<vector>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=2e5+11;
int N,K,W[MAXN],Lim,A[MAXN],f[MAXN],Siz[MAXN],siz[MAXN]; vector<int> vec[MAXN];
void dfs(int u,int fath){
    Siz[u]=(A[u]),siz[u]=1; int Maxn=0;
    for(auto v:vec[u]){
        if(v==fath) continue;dfs(v,u);
        Siz[u]+=Siz[v],siz[u]+=siz[v];
        if(A[u]){
            if(Siz[v]==siz[v]) f[u]+=siz[v];
            else Maxn=max(Maxn,f[v]);
        }
    }
    if(A[u]) f[u]+=Maxn+1; return;
}
bool ff;
void dfs1(int u,int fath){
    int t=siz[u];siz[u]=N;
    if(A[u]){
        int Maxn=0,Ans=0;
        for(auto v:vec[u]){
            if(Siz[v]==siz[v]) Ans+=siz[v];
            else Maxn=max(Maxn,f[v]);
        }
        f[u]=Maxn+Ans+1;
        if(Maxn+Ans+1>=K) ff=1;
    }int s=f[u];
    int Maxn1=0,Maxn2=0;
    for(auto v:vec[u]){
        if(Siz[v]!=siz[v]){
            if(f[v]>=Maxn1) Maxn2=Maxn1,Maxn1=f[v];
            else if(f[v]>Maxn2) Maxn2=f[v];
        }
    }
    for(auto v:vec[u]){
        if(v==fath) continue;
        siz[u]-=siz[v];
        if(!A[u]){
            Siz[u]-=Siz[v];
            Siz[v]+=Siz[u];
            dfs1(v,u);
            Siz[v]-=Siz[u];
            Siz[u]+=Siz[v];
        }
        else if(siz[v]==Siz[v]&&A[u]){
            Siz[u]-=Siz[v];
            f[u]-=siz[v];
            Siz[v]+=Siz[u];
            dfs1(v,u);
            f[u]+=siz[v];
            Siz[v]-=Siz[u];
            Siz[u]+=Siz[v];
        }else{
            if(f[v]==Maxn1){
                f[u]-=Maxn1;f[u]+=Maxn2;
                Siz[u]-=Siz[v];
                Siz[v]+=Siz[u];
                dfs1(v,u);
                Siz[v]-=Siz[u];
                f[u]+=Maxn1;f[u]-=Maxn2;
                Siz[u]+=Siz[v];
            }else{
                Siz[u]-=Siz[v];
                Siz[v]+=Siz[u];
                dfs1(v,u);
                Siz[v]-=Siz[u];
                Siz[u]+=Siz[v];
            }
        }
        siz[u]+=siz[v];
    }siz[u]=t;return;
}
bool check(){//>=mid    
    ff=0;for(int i=1;i<=N;i++) A[i]=(W[i]>=Lim);
    memset(siz,0,sizeof(siz)),memset(f,0,sizeof(f)),memset(Siz,0,sizeof(Siz));
    dfs(1,0);
    dfs1(1,0);
    return ff;
}
int main(){
    N=read(),K=read(); for(int i=1;i<=N;i++) W[i]=read();
    for(int i=1;i<N;i++){int u=read(),v=read();vec[u].pb(v),vec[v].pb(u);}
    int l=1,r=1e6,res=-1;
    while(l<=r){
        int mid=(l+r)>>1;Lim=mid;
        if(check()) res=mid,l=mid+1;
        else r=mid-1;
    } printf("%d
",res);return 0;
}/*
5 3
3 6 1 4 2
1 2
2 4
2 5
1 3
*/
View Code

 [x] CF1373F

题意：有 $n$ 个城市和发电站，第 $i$ 个城市需要 $a_i$​ 个单位的电，第 $i$ 个发电站可以给第 $i$ 或 $i+1$ 个城市供电（第 $n$ 个给的是 $n$ 和 $1$），这个发电站给两城市供电总量最多 $b_i$ 个单位，问是否能满足所有城市的需求。

降智题目。可以设 $x_i$ 表示 $b_i$ 给 $a_i$ 的电量，差分约束判特殊图即可。

还可以设枚举 $x_1$ 的值，可以发现若中途出现不够则肯定要比当前值小，若最后不能满足 $1$ 的要求则要提升 $x$ ，时间复杂度 $O(n)$。

可以发现这个过程能用二分优化，时间复杂度 $O(nlog n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e6+11;
int T,A[MAXN],B[MAXN],N;
int check(int xx){
    int res=B[1]-xx;
    for(int i=2;i<=N;i++){
        if(res+B[i]<A[i]) return 1;
        res=min(res+B[i]-A[i],B[i]);
    }    
    if(res+xx<A[1]) return 2;
    return 0;
}
int main(){
    //freopen("4.in","r",stdin);
    T=read();
    while(T--){
        N=read(); for(int i=1;i<=N;i++) A[i]=read(); for(int i=1;i<=N;i++) B[i]=read();
        int l=0,r=B[1]; bool ff=0;
        while(l<=r){
            int mid=(l+r)>>1,t=check(mid);
            if(!t){printf("YES
");ff=1;break;}
            if(t==1) r=mid-1;
            else l=mid+1;
        }if(!ff) printf("NO
");
    }return 0;
}/*
1
4 3 3 1 2 1 2 6 4 4 
2 5 3 5 4 4 5 6 2 4 
*/
View Code

[] CF1209

题意：给定一个 $n imes m$ 的矩阵，你可以对每一列进行若干次循环移位 求操作完成后每一行的最大值之和。

可以发现我们只需要枚举最大值最大的前 $n$ 列，因为对于其他元素我们可以通过调整用前 $n$ 列的值替换他。

故设 $f_{i,S}$ 表示当前在第 $i$ 列，选择行的状态为 $j$ 的最大值，预处理循环移位后 $dp$ 即可。

时间复杂度 $O(n imes 3^n)$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=13;
const int MAXM=2001;
int N,M,A[MAXN][MAXM],id[MAXM],tmp[MAXM],T,Maxn[MAXM],rnk[MAXM],W[MAXN][1<<MAXN],f[MAXN][1<<MAXN];
bool cmp(int x,int y){return Maxn[x]>Maxn[y];}
int main(){
    //freopen("1.in","r",stdin);
    T=read();while(T--){
        memset(Maxn,0,sizeof(Maxn)),memset(W,0,sizeof(W));
        N=read(),M=read(); for(int i=1;i<=M;i++) rnk[i]=i;
        for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) A[i][j]=read(),Maxn[j]=max(Maxn[j],A[i][j]);
        sort(rnk+1,rnk+M+1,cmp); int K=min(N,M);
        for(int i=1;i<=K;i++){
            int ps=rnk[i];
            //cerr<<"ps:"<<ps<<endl;
            for(int j=0;j<N;j++){
                int cnt=0;
                for(int p=1;p<=N;p++){
                    int t=(j+p)%N; if(!t) t=N;
                    tmp[cnt++]=(A[t][ps]);
                }
                //for(int z=0;z<N;z++) printf("%d ",tmp[z]);printf("
");
                for(int sta=0;sta<(1<<N);sta++){
                    int s=0; for(int z=0;z<N;z++) if(sta&(1<<z)) s+=tmp[z];
                    W[i][sta]=max(W[i][sta],s);
                }
            }
        }memset(f,-127/3,sizeof(f)); f[0][0]=0;
        for(int i=1;i<=K;i++){
            for(int j=0;j<(1<<N);j++){
                f[i][j]=f[i-1][j];
                for(int k=j;k;k=(k-1)&j){
                    f[i][j]=max(f[i][j],f[i-1][j^k]+W[i][k]);
                }
            }                
        }printf("%d
",f[K][(1<<N)-1]);
        //return 0;
    }return 0;
}/*
3
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7
3 3
9 9 9
1 1 1
1 1 1
*/
View Code

 [] CF1257F

题意：求是否存在 $x (0leq x leq 2^{30}-1)$ ，使得对于数组 $b_i$ ​，其中 $b_i=a_i ext{ xor } x$，$b_i$​ 中所有元素两两的 $ ext{popcount}(b_i)$ 相同。

考虑对前 $15$ 位后 $15$ 位折半搜索，用 $map$ 查询即可。为啥是 $F$ 题？

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=101;
int lowbit(int x){return x&-x;}
int cont(int x){int c=0;while(x) c++,x-=lowbit(x);return c;}
int N,A[MAXN];
vector<int> sta;
map<vector<int> ,int> M;
int main(){
    N=read();for(int i=1;i<=N;i++) A[i]=read();
    for(int i=0;i<(1<<15)-1;i++){
        int cur=cont(i^((A[1]>>15)));sta.clear();
        for(int j=1;j<=N;j++) sta.push_back(cont(i^(A[j]>>15))-cur);
        M[sta]=i;
    }
    int all=((1<<15)-1);
    for(int i=0;i<(1<<15)-1;i++){
        int cur=cont(i^((A[1]&all)));sta.clear();
        for(int j=1;j<=N;j++) sta.push_back(cur-cont(i^(A[j]&all)));
        if(M.count(sta)){
            printf("%d
",(M[sta]<<15)+i);
            return 0;
        }
    }printf("-1
");return 0;
}
View Code

 [x] CF1244G

题意：找出两个 $1$ 到 $n$ 的全排列 $p$ 和 $q$ ，使得  $sum^n_{i=1} max(p_i,q_i)$ 尽量大且不超过给定的 $k$ 。

可以发现可以取到的区间为 $[sum i,sum max(i,N-i)]$ ，其中每个点都能取到。微调即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e6+11;
int N,A[MAXN],B[MAXN],K;
signed main(){
    N=read(),K=read();
    if(K<N*(N+1)/2){printf("-1
");return 0;}
    int Ans=N*(N+1)/2; for(int i=1;i<=N;i++) A[i]=i;
    int L=1,R=N;
    //cerr<<"Ans:"<<Ans<<endl;
    for(int i=1;i<=N;i++){
        if(R>=i&&R-i+Ans<=K){B[i]=R;Ans+=R-i;R--;}
        else{B[i]=L,L++;}
    }
    printf("%lld
",Ans);
    for(int i=1;i<=N;i++) printf("%lld ",A[i]);printf("
");
    for(int i=1;i<=N;i++) printf("%lld ",B[i]);printf("
");
    return 0;
}
View Code

[] CF1348E

题意：他一共有$n$ 棵树，第 $i$ 棵树上有 $a_i$ ​ 个红梅和 $b_i$ ​ 个蓝莓。由于小 $P$ 有强迫症，所以他希望一个篮子里的梅子都来自同一棵树或都是一种颜色的（或两者同时满足）。 给出篮子的最大容量 $k$ ，求能够被装满的篮子数量的最大值（不必用完所有梅子）

设 $f_{i,j,k}$ 表示当前在 $i$ 点，红树剩 $j$ 个，蓝树剩 $k$ 个的最大值，可以发现对于 $i$ 固定 $j+k$ 是个定值，缩掉因为后暴力 $dp$ 即可，时间复杂度 $O(n^2k)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=501;
int N,K,A[MAXN],B[MAXN],sum;
int Mod(int x){
    if(x>=0){return x>=K?x-K:x;}
    x+=K;
    return x>K?x-K:x;
}
LL f[2][MAXN],Maxn;
int main(){
    //freopen("4.in","r",stdin);
    N=read(),K=read(); for(int i=1;i<=N;i++) A[i]=read(),B[i]=read();
    memset(f,-127/3,sizeof(f)); f[0][0]=0; int cur=0;
    for(int i=0;i<N;i++){
        cur^=1;memset(f[cur],-127/3,sizeof(f[cur]));
        int ss=(A[i+1]+B[i+1])%K;
        for(int j=0;j<K;j++){
            if(f[cur^1][j]<0) continue;
            int z=Mod(sum-j);
            for(int p=0;p<K;p++){
                int s=Mod(ss-p);
                if(A[i+1]<p||B[i+1]<s) continue;
                int sum1=(j+p),sum2=(z+s),ff=Mod(sum1);
                f[cur][ff]=max(f[cur][ff],f[cur^1][j]+(sum1/K)+(sum2/K)+(A[i+1]+B[i+1]-p-s)/K);
            }
            
        }sum+=A[i+1]+B[i+1],sum%=K;
    }
    for(int i=0;i<K;i++) Maxn=max(Maxn,f[cur][i]);
    printf("%lld
",Maxn); return 0;
}/*
3 5
1 1
0 2
7 1
*/
View Code

 [] CF1221F

题意：选一个正方形，该正方形的左下角及右上角必须在 $y=x$ 这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角 $x_1,y_1$ ​及右上角 $x_2,y_2$ 。​

考虑 $i$ 号点可以做贡献的区域，设 $x_igeq y_i$ ，则 $x1leq y_i,x2geq x_i$ 即可。

可以发现将其投射到矩形中转换成求 $val_{i,j}-(j-i)$  ，扫描线维护，时间复杂度 $O(nlog n)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<vector>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e6+11; vector<pair<pii,int> > vec[MAXN];
int tmp[MAXN],N,X[MAXN],Y[MAXN],W[MAXN],M;
pii operator+(pii x1,pii x2){if(x1.fi>x2.fi) return x1;return x2;}
struct Segment{
    int Maxn[MAXN<<2],ps[MAXN<<2],tag[MAXN<<2];
    void pushup(int k){
        if(Maxn[k<<1]>=Maxn[k<<1|1]) Maxn[k]=Maxn[k<<1],ps[k]=ps[k<<1];
        else Maxn[k]=Maxn[k<<1|1],ps[k]=ps[k<<1|1]; return;
    }
    void pushdown(int k){
        if(!tag[k]) return;
        Maxn[k<<1]+=tag[k],Maxn[k<<1|1]+=tag[k];
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
        tag[k]=0; return;
    }
    void build(int k,int l,int r){
        if(l==r){Maxn[k]=-tmp[l];ps[k]=l;return;}
        int mid=(l+r)>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r);
        pushup(k); return;
    }
    void Add(int k,int l,int r,int x,int y,int w){
        if(x<=l&&r<=y){tag[k]+=w;Maxn[k]+=w;return;}
        pushdown(k); int mid=(l+r)>>1;
        if(x<=mid) Add(k<<1,l,mid,x,y,w); if(mid<y) Add(k<<1|1,mid+1,r,x,y,w);
        pushup(k); return;
    }
    pii Query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return mp(Maxn[k],ps[k]);
        pushdown(k); int mid=(l+r)>>1; pii res=mp(LLONG_MIN,0);
        if(x<=mid) res=res+Query(k<<1,l,mid,x,y);
        if(mid<y) res=res+Query(k<<1|1,mid+1,r,x,y);
        pushup(k); return res;
    }
}S;
int a,b;
signed main(){
    //freopen("1.in","r",stdin);
    N=read(); for(int i=1;i<=N;i++) tmp[++tmp[0]]=X[i]=read(),tmp[++tmp[0]]=Y[i]=read(),W[i]=read();
    sort(tmp+1,tmp+tmp[0]+1); M=unique(tmp+1,tmp+tmp[0]+1)-tmp-1;
    for(int i=1;i<=N;i++) X[i]=lower_bound(tmp+1,tmp+M+1,X[i])-tmp,Y[i]=lower_bound(tmp+1,tmp+M+1,Y[i])-tmp;
    S.build(1,1,M);
    for(int i=1;i<=N;i++){
        if(X[i]>=Y[i]) vec[1].pb(mp(mp(X[i],M),W[i])),vec[Y[i]+1].pb(mp(mp(X[i],M),-W[i]));
        else vec[1].pb(mp(mp(Y[i],M),W[i])),vec[X[i]+1].pb(mp(mp(Y[i],M),-W[i]));
    } int Maxn=-LLONG_MAX;
    for(int i=1;i<=M;i++){
        for(auto pp:vec[i]) S.Add(1,1,M,pp.fi.fi,pp.fi.se,pp.se);
        pii p=S.Query(1,1,M,i,M); int W=p.fi+tmp[i];
        if(W>Maxn){
            Maxn=W;a=tmp[i],b=tmp[p.se];
        }
        Maxn=max(Maxn,p.fi+tmp[i]);
    }
    if(Maxn<0) Maxn=0,a=tmp[M]+1,b=tmp[M]+1;
    printf("%lld
%lld %lld %lld %lld
",Maxn,a,a,b,b); return 0;
}/*
5
3 3 0
3 3 -3
0 2 -1
0 0 -2
*/
View Code

 [x] CF1065F

题意：有一个以 $1$ 为根的含 $n$ 个节点的树，每次可以走到一个叶子，然后可以往上（祖先）走 $k$ 步，重复此过程。问最多走多少个叶子。

之前做过。设 $f_u$ 表示以 $u$ 为根的子树起点在 $u$ 最多走多少个，则 $f_u=sum [low_v-kleq dep_u]f_v$ 。

则我们最后需要处理 $1$ 走到哪个子树出不去，递归完成即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1000001;
int n,head[MAXN],d[MAXN],Ans[MAXN],f[MAXN],k,dep[MAXN],low[MAXN],cnt,INF=INT_MAX;
struct node{
    int u,v,nex;
}x[MAXN<<1];
void add(int u,int v){
    d[u]++;
    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;
}
void dfs1(int u,int fath){
    dep[u]=dep[fath]+1;
    if(!d[u]){f[u]=1,low[u]=dep[u];return;}
    low[u]=INF;
    for(int i=head[u];i!=-1;i=x[i].nex){
        if(x[i].v==fath) continue;
        dfs1(x[i].v,u);
        if(low[x[i].v]-dep[u]<=k) f[u]+=f[x[i].v],low[u]=min(low[u],low[x[i].v]);
    }
    
}
void dfs2(int u,int fath){
    Ans[u]=f[u];
    for(int i=head[u];i!=-1;i=x[i].nex){
        if(x[i].v==fath) continue;
        dfs2(x[i].v,u);
        int v=x[i].v;
        int tmp=f[u];if(low[x[i].v]-dep[u]<=k) tmp-=f[v];
        Ans[u]=max(Ans[u],tmp+Ans[v]);
    }return;
}
int main(){
//    freopen("5.in","r",stdin);
    memset(head,-1,sizeof(head));
    n=read(),k=read();
    for(int i=2;i<=n;i++) add(read(),i);
    dfs1(1,0);
    dfs2(1,0);
    printf("%d
",Ans[1]);return 0;
}/*
8 2
1 1 2 3 4 5 5
*/
View Code

[] CF1221F

题意：让你选一个正方形，该正方形的左下角及右上角必须在 $y=x$ 。这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角 $x_1,y_1$ 及右上角 $x_2,y_2$​ ，要求 $0le x_1=y_1le x_2=y_2le 2cdot 10^9$ 。

设点 $(x,y)space xgeq y$ ，则若点被包含在正方形内则 $lin[1,y],rin [x,10^9]$ ，可以把这个看成矩形加，扫描线维护即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<vector>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e6+11; vector<pair<pii,int> > vec[MAXN];
int tmp[MAXN],N,X[MAXN],Y[MAXN],W[MAXN],M;
pii operator+(pii x1,pii x2){if(x1.fi>x2.fi) return x1;return x2;}
struct Segment{
    int Maxn[MAXN<<2],ps[MAXN<<2],tag[MAXN<<2];
    void pushup(int k){
        if(Maxn[k<<1]>=Maxn[k<<1|1]) Maxn[k]=Maxn[k<<1],ps[k]=ps[k<<1];
        else Maxn[k]=Maxn[k<<1|1],ps[k]=ps[k<<1|1]; return;
    }
    void pushdown(int k){
        if(!tag[k]) return;
        Maxn[k<<1]+=tag[k],Maxn[k<<1|1]+=tag[k];
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
        tag[k]=0; return;
    }
    void build(int k,int l,int r){
        if(l==r){Maxn[k]=-tmp[l];ps[k]=l;return;}
        int mid=(l+r)>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r);
        pushup(k); return;
    }
    void Add(int k,int l,int r,int x,int y,int w){
        if(x<=l&&r<=y){tag[k]+=w;Maxn[k]+=w;return;}
        pushdown(k); int mid=(l+r)>>1;
        if(x<=mid) Add(k<<1,l,mid,x,y,w); if(mid<y) Add(k<<1|1,mid+1,r,x,y,w);
        pushup(k); return;
    }
    pii Query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return mp(Maxn[k],ps[k]);
        pushdown(k); int mid=(l+r)>>1; pii res=mp(LLONG_MIN,0);
        if(x<=mid) res=res+Query(k<<1,l,mid,x,y);
        if(mid<y) res=res+Query(k<<1|1,mid+1,r,x,y);
        pushup(k); return res;
    }
}S;
int a,b;
signed main(){
    //freopen("1.in","r",stdin);
    N=read(); for(int i=1;i<=N;i++) tmp[++tmp[0]]=X[i]=read(),tmp[++tmp[0]]=Y[i]=read(),W[i]=read();
    sort(tmp+1,tmp+tmp[0]+1); M=unique(tmp+1,tmp+tmp[0]+1)-tmp-1;
    for(int i=1;i<=N;i++) X[i]=lower_bound(tmp+1,tmp+M+1,X[i])-tmp,Y[i]=lower_bound(tmp+1,tmp+M+1,Y[i])-tmp;
    S.build(1,1,M);
    for(int i=1;i<=N;i++){
        if(X[i]>=Y[i]) vec[1].pb(mp(mp(X[i],M),W[i])),vec[Y[i]+1].pb(mp(mp(X[i],M),-W[i]));
        else vec[1].pb(mp(mp(Y[i],M),W[i])),vec[X[i]+1].pb(mp(mp(Y[i],M),-W[i]));
    } int Maxn=-LLONG_MAX;
    for(int i=1;i<=M;i++){
        for(auto pp:vec[i]) S.Add(1,1,M,pp.fi.fi,pp.fi.se,pp.se);
        pii p=S.Query(1,1,M,i,M); int W=p.fi+tmp[i];
        if(W>Maxn){
            Maxn=W;a=tmp[i],b=tmp[p.se];
        }
        Maxn=max(Maxn,p.fi+tmp[i]);
    }
    if(Maxn<0) Maxn=0,a=tmp[M]+1,b=tmp[M]+1;
    printf("%lld
%lld %lld %lld %lld
",Maxn,a,a,b,b); return 0;
}/*
5
3 3 0
3 3 -3
0 2 -1
0 0 -2
*/
View Code

 [] CF571D

模拟赛写三小时。。。最后还挂掉了。。。

题意：维护两个下标集合 ${a},{b}$，支持合并，使 $a$ 中 $x$ 所在的集合所有元素加 $x$，或使 $b$ 中 $x$ 所在的集合全赋值为 $x$，单点查询。

考虑对 $a,b$ 分别建重构树，则问题转换为树上结点所包含的叶子区间加，区间赋值。但是两树的 $dfs$ 序是不同的，则可以先查找被 $b$ 赋到了多少在查询 $a$ 树的情况。

对于 $b$ 树可以直接那线段树维护，而 $a$ 树由于有时间限制相当于二维输点直接维护即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<vector>
#define LL long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e6+11;
int N,Q,tot,rev[MAXN],siz[MAXN],dfn[MAXN],vis[MAXN]; vector<int> vecA[MAXN],vecB[MAXN];
LL Ans[MAXN];
struct Segment{
    int tag[MAXN<<2];
    void pushdown(int k){
        if(tag[k]==-1) return;
        tag[k<<1]=tag[k],tag[k<<1|1]=tag[k];
        tag[k]=-1;return;
    }
    void Cover(int k,int l,int r,int x,int y,int w){
        if(x<=l&&r<=y){tag[k]=w;return;}
        pushdown(k); int mid=(l+r)>>1;
        if(x<=mid) Cover(k<<1,l,mid,x,y,w); if(mid<y) Cover(k<<1|1,mid+1,r,x,y,w);
        return;
    }
    int Query(int k,int l,int r,int ps){
        if(l==r) return tag[k];
        pushdown(k); int mid=(l+r)>>1;
        if(ps<=mid) return Query(k<<1,l,mid,ps);
        if(mid<ps) return Query(k<<1|1,mid+1,r,ps);
    }
}SB;
struct BIT{
    LL Ans[MAXN];
    int lowbit(int x){return x&-x;}
    void Modify(int x,int w){for(;x<=N;x+=lowbit(x)) Ans[x]+=w;return;}
    void Add(int l,int r,int w){if(l>r) return;Modify(l,w),Modify(r+1,-w);return;}
    LL Query(int x){LL res=0;for(;x;x-=lowbit(x)) res+=Ans[x];return res;}
}SA;
struct Union{
    int f[MAXN<<1],siz[MAXN];
    void init(){for(int i=1;i<=(N<<1);i++) f[i]=i,siz[i]=1;return;}
    int find(int xx){return f[xx]==xx?xx:f[xx]=find(f[xx]);}
    void merge(int x,int y){
        int t1=find(x),t2=find(y);
        f[t2]=t1;siz[t1]+=siz[t2];return;
    }
}UA,UB,U;
struct Query{
    int opt,x,y,rt;
}Que[MAXN];
void dfs(int u){
    vis[u]=1;if(u<=N){dfn[u]=++dfn[0],rev[dfn[0]]=u;siz[u]=1;return;} dfn[u]=dfn[0]+1;
    for(auto v:vecB[u]) dfs(v),siz[u]+=siz[v]; return;
}
int dfn1[MAXN],rev1[MAXN],siz1[MAXN];
void dfs1(int u){
    vis[u]=1;if(u<=N){dfn1[u]=++dfn1[0],rev1[dfn1[0]]=u;siz1[u]=1;return;} dfn1[u]=dfn1[0]+1;
    for(auto v:vecA[u]) dfs1(v),siz1[u]+=siz1[v];
}
struct Real{
    int L,R,W,tim;
    int opt,id;
}Quee[MAXN];
bool cmp(Real x1,Real x2){
    if(x1.tim==x2.tim) return abs(x1.opt)<abs(x2.opt);
    return x1.tim<x2.tim;
}char str[4];
signed main(){
    //freopen("A.in","r",stdin);
    N=read(),Q=read(); UA.init(),UB.init();U.init();
    for(int i=1;i<=Q;i++){
        scanf("%s",str+1);int opt;
        if(str[1]=='U') opt=1;
        if(str[1]=='M') opt=2;
        if(str[1]=='A') opt=3;
        if(str[1]=='Z') opt=4;
        if(str[1]=='Q') opt=5;
        Que[i].opt=opt;
        if(opt<=2) Que[i].x=read(),Que[i].y=read();
        if(opt==1) U.merge(Que[i].x,Que[i].y);
        else if(opt>=3){
            Que[i].x=read();
            if(opt==4) Que[i].y=0;
            if(opt==3){
                Que[i].y=U.siz[U.find(Que[i].x)];
            }
        }
    } int cntA=N,cntB=N;
    for(int i=1;i<=Q;i++){
        if(Que[i].opt==1){
            int u=Que[i].x,v=Que[i].y,tu=UA.find(u),tv=UA.find(v);
            cntA++; vecA[cntA].pb(tu),vecA[cntA].pb(tv);UA.f[tu]=cntA,UA.f[tv]=cntA;
        }
        if(Que[i].opt==2){
            int u=Que[i].x,v=Que[i].y,tu=UB.find(u),tv=UB.find(v);
            cntB++; vecB[cntB].pb(tu),vecB[cntB].pb(tv);UB.f[tu]=cntB,UB.f[tv]=cntB;
        }
        if(Que[i].opt==3) Que[i].rt=UA.find(Que[i].x);
        if(Que[i].opt==4) Que[i].rt=UB.find(Que[i].x);
    }
    memset(vis,0,sizeof(vis)); for(int i=cntB;i>=1;i--) if(!vis[i]) dfs(i);
    memset(vis,0,sizeof(vis)); for(int i=cntA;i>=1;i--) if(!vis[i]) dfs1(i);
    //cerr<<dfn1[2]<<endl;return 0;
    for(int i=1;i<=Q;i++){
        if(Que[i].opt<=2) continue;
        if(Que[i].opt==3){
            ++tot; int rt=Que[i].rt;
            Quee[tot].L=dfn1[rt],Quee[tot].R=dfn1[rt]+siz1[rt]-1;
            Quee[tot].W=Que[i].y;Quee[tot].tim=i;
            continue;
        }
        if(Que[i].opt==4){
            int rt=Que[i].rt;
            SB.Cover(1,1,N,dfn[rt],dfn[rt]+siz[rt]-1,i);
            continue;
        }
        int u=Que[i].x,p=SB.Query(1,1,N,dfn[u]);
        int L=p+1,R=i-1;
        Ans[i]=Que[p].y;
        ++tot;Quee[tot].opt=-1,Quee[tot].id=i,Quee[tot].tim=L-1;
        ++tot;Quee[tot].opt= 1;Quee[tot].id=i,Quee[tot].tim=R;
    } sort(Quee+1,Quee+tot+1,cmp);int ps=1;
     for(int i=0;i<=Q;i++){
        while(ps<=tot&&Quee[ps].tim==i){
            if(!Quee[ps].opt){SA.Add(Quee[ps].L,Quee[ps].R,Quee[ps].W);ps++;continue;}
            LL id=Quee[ps].id,opt=Quee[ps].opt,W=SA.Query(dfn1[Que[id].x]);
            //cerr<<"W:"<<W<<" "<<dfn1[Que[id].x]<<endl;
            Ans[id]+=opt*W; ps++;
        }
    }
    for(int i=1;i<=Q;i++) if(Que[i].opt==5) printf("%lld
",Ans[i]);
    return 0;
}/*
3 5
2 1 1
3 3 1
3 3 3
4 1 4
5 2
*/
View Code

[x] CF1450C

题意：一个$n * n$的棋盘上有$'.'$和$'X'$和$‘O’$，三个$'X'$或者三个$'O'$横着或竖着连续，则算赢局，否则算平局，给出一个局面，现在你需要把最多$lfloor frac{k}{3} floor$的位置（$k$为$'X'$的个数）改成$'O'$，反之亦然，让它变成平局，输出方案。

日常降智。

考虑三个连续的必然是 $x+y$ 的和对 $3$ 取余的结果是 $0,1,2$ ，则一个简单的想法是将一个消掉。可以发现我们只需要对 $X,O$ 找到一组余数不相等最小的改变即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<set>
#include<vector>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=311;
char str[MAXN];
int T,N,x[4],o[4],A[MAXN][MAXN]; vector<pii> vec[2][4];
int main(){
    //freopen("in1.txt","r",stdin);
    T=read();
    while(T--){
        memset(x,0,sizeof(x)),memset(o,0,sizeof(o));
        N=read(); for(int i=0;i<3;i++) for(int j=0;j<=1;j++) vec[j][i].clear();
        for(int i=1;i<=N;i++){
            scanf("%s",str+1);
            for(int j=1;j<=N;j++){
                int res=(i+j)%3;
                if(str[j]=='X') A[i][j]=0,x[res]++,vec[0][res].pb(mp(i,j));
                if(str[j]=='O') A[i][j]=1,o[res]++,vec[1][res].pb(mp(i,j));
                if(str[j]=='.') A[i][j]=-1;
            }
        }int ps1=-1,ps2=-1,Minn=INT_MAX;
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++){
                if(i==j) continue;
                if(x[i]+o[j]<=Minn) Minn=x[i]+o[j],ps1=i,ps2=j;
            }
        }
        for(auto pp:vec[0][ps1]) A[pp.fi][pp.se]^=1;
        for(auto pp:vec[1][ps2]) A[pp.fi][pp.se]^=1;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(A[i][j]==0) printf("X");
                if(A[i][j]==1) printf("O");
                if(A[i][j]==-1) printf(".");
            }printf("
");
        }
    }return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/si-rui-yang/p/14045032.html