【题解】毒瘤 OI 刷题汇总 [SCOI2015]

2023-12-15 11:35:39

【题解】毒瘤 OI 刷题汇总 [SCOI2015]

由于不清楚题目顺序，就按照 \(\text{BZOJ}\) 上面的排列好了。

【Day1 T1】小凸玩矩阵

传送门：小凸玩矩阵 \(\text{[P4251]}\) \(\text{[Bzoj4443]}\)

【题目描述】

给出一个 \(n\times m\) \((1\leqslant n\leqslant m\leqslant 250)\) 的矩阵 \(a\)，现要从中选出 \(n\) 个数，且满足任意两个数都不能在同一行或同一列。求选出的 \(n\) 个数中第 \(k\) \((1\leqslant k\leqslant n)\) 大的数最下可以为多少。

【分析】

二分+最大匹配判定。

求第 \(k\) 大最小很明显可以二分，判定二分值 \(mid\) 的优劣性时可以上最大匹配。由于答案要尽量小，所以大于 \(mid\) 的数要尽量少选，小于等于 \(mid\) 的数要尽量多选，考虑使用后者作为判定依据（方便跑最大匹配）。

在每次判定中，对于 \(a_{i,j}\leqslant mid\) 的位置，\(i\) 向 \(j\) 连边，跑出的最大匹配就是小于等于 \(mid\) 的数最多可以选出的数量。

设最终答案为 \(ans\)，如果至少可以选出 \(n-k+1\) 个（最大匹配 \(\geqslant n-k+1\)），说明 \(mid\geqslant ans\)，缩小上界，反之扩大下界。

跑最大匹配我一般都用 \(dinic\)，复杂度更优一点。但这道题用匈牙利貌似也能过。

时间复杂度：\(O(n^2\log n)\) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=505,M=63005,inf=2e9;
int n,m,l,r,K,st,ed,A[253][253];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Dinic{
    int o,h,t,maxflow,Q[N],dis[N],cur[N],head[N];
    inline void CL(){memset(head,0,sizeof(head)),maxflow=0,o=1;}
    struct QAQ{int to,next,flow;}a[M<<1];
    inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
    inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
    inline int bfs(Re st,Re ed){
        for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
        h=1,t=0,Q[++t]=st,dis[st]=1;
        while(h<=t){
            Re x=Q[h++];
            for(Re i=head[x],to;i;i=a[i].next)
                if(a[i].flow&&!dis[to=a[i].to]){
                    dis[to]=dis[x]+1,Q[++t]=to;
                    if(to==ed)return 1;
                }
        }
        return 0;
    }
    inline int dfs(Re x,Re flow){
        if(x==ed||!flow)return flow;
        Re tmp=0,to,f;
        for(Re i=cur[x];i;i=a[i].next){
            cur[x]=i;
            if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
                a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
                if(flow==tmp)break;
            }
        }
        return tmp;
    }
    inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
}T1;
inline int judge(Re X){
    T1.CL(),st=n+m+1,ed=st+1;
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            if(A[i][j]<=X)T1.add(i,n+j,1);
    for(Re i=1;i<=n;++i)T1.add(st,i,1);
    for(Re i=1;i<=m;++i)T1.add(n+i,ed,1);
    T1.dinic(st,ed);
    return T1.maxflow>=n-K+1;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m),in(K),l=inf,r=0;
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            in(A[i][j]),l=min(l,A[i][j]),r=max(r,A[i][j]);
    while(l<r){
        Re mid=l+r>>1;
        if(judge(mid))r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
}

【Day1 T2】国旗计划

传送门：国旗计划 \(\text{[P4155]}\) \(\text{[Bzoj4444]}\)

【题目描述】

有一个大小为 \(m\) \((m<10^9)\) 的环，环上的点编号分别为 \(1,2,3...m\)，现给出 \(n\) \((n\leqslant 2*10^5)\) 个线段（不会有互相包含的情况），您需要选出最少的线段覆盖整个环。求在必选线段 \(i\) 时所需要的最小线段个数。

【分析】

暴力倍增。

按照套路先将环复制一遍变成链。

把所有线段按照左端点排个序，对于每一个线段 \(i\)，右边与它相交的线段都可以作为接力的候选人，但由于线段不会互相包含，所以直接贪心选最右边的那一个。这个东西直接用一个指针扫过去就搞定了。

考虑对于每次询问 \(i\)，以线段 \(i\) 的左端点作为起点，然后不断地往后跳，直至区间右端点大于等于 \(i+m\) 时就结束。酱紫的暴力当然是不行的，但可以用倍增优化跳跃的过程。

时间复杂度：\(O(n\log n)\) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,logN=19;
int n,m,x,y,nex[N<<1],Ans[N],f[N<<1][20];
struct QAQ{int l,r,id;inline bool operator<(const QAQ &O)const{return l<O.l;};}A[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m);
    for(Re i=1;i<=n;++i){
        in(x),in(y);if(x>y)y+=m;
        A[i]=(QAQ){x,y,i},A[i+n]=(QAQ){x+m,y+m,i};
//注意所有区间都必须复制一遍(右端点大于m的也必须加，否则洛咕第2个点会WA)
    }
    n<<=1,sort(A+1,A+n+1);
    for(Re i=1,j=1;i<=n;++i){
        while(j<n&&A[j+1].l<=A[i].r)++j;
        nex[i]=j;if(i<j)f[i][0]=j;
    }
    for(Re j=1;j<=logN;++j)
        for(Re i=1;i+(1<<j)<=n;++i)
            f[i][j]=f[f[i][j-1]][j-1];
    for(Re i=1;i<=(n>>1);++i){
        Re tmp=1,now=i;
        for(Re j=logN;j>=0;--j)
            if(f[now][j]&&A[f[now][j]].r<A[i].l+m)
                tmp+=(1<<j),now=f[now][j];
        Ans[A[i].id]=tmp+1;
    }
    for(Re i=1;i<=(n>>1);++i)printf("%d ",Ans[i]);
}

【Day1 T3】小凸想跑步

传送门：小凸想跑步 \(\text{[P4250]}\) \(\text{[Bzoj4445]}\)

【题目描述】

给出一个 \(n\) \((n\leqslant 10^5)\) 个点的凸包，在凸包内任选一个点 \(A\)，将 \(A\) 与凸包上的点 \(P_{i\in[1,n]}\) 连边，构成 \(n\) 个三角形。设 \(P_{n+1}=P_1\)，若对于任意的 \(i\in[2,n]\) 均满足 \(S_{\Delta AP_1P_2}\leqslant S_{\Delta AP_iP_{i+1}}\)，则称点 \(A\) 合法。求任选一个点的合法概率。

【分析】

暴力化简柿子 + 半平面交。

考虑将上面的不等式展开（注意 \(x\times y=-y\times x\)）：

\[S_{\Delta AP_1P_2}\leqslant S_{\Delta AP_iP_{i\%n+1}}\\ (P_1-A)\times(P_2-A)\leqslant (P_i-A)\times(P_{i+1}-A)\\ P_1\times P_2 +P_1\times (-A)+(-A)\times P2\leqslant P_i\times P_{i+1} +P_i\times (-A)+(-A)\times P{i+1}\\ P_1\times P_2+A\times (P_1-P_2)\leqslant P_i\times P_{i+1}+A\times (P_i-P_{i+1})\\ A\times (P_1-P_2-P_i+P_{i+1})+P_1\times P_2-P_i\times P_{i+1}\leqslant 0 \]

设 \(A(x,y)\)，则上述式子可表示为 \(ax+by+c\leqslant 0\) 的形式，其中 \(a=(P_1-P_2-P_i+P_{i+1})_y,\) \(b=-(P_1-P_2-P_i+P_{i+1})_x,\) \(c=P_1\times P_2-P_i\times P_{i+1}\)，用半平面交把这堆不等式方程组解出来就可以得到合法区域。

具体来说，对于每个 \(i\in[2,n]\)：讨论一下 \(a,b\) 的正负性，分别选择合适的半平面向量，最后再把凸多边形的边界也加进去（要求选点只能在凸包里面），用解出的小凸包与原凸包面积求比值即为答案。

时间复杂度：\(O(n\log n)\) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline int judge(Point a,Point L,Point R){//判断AL是否在AR右边
    return dcmp(Cro(L-a,R-a))>0;
}
inline Point cross(Point a,Point b,Point c,Point d){
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));
}
inline LD PolyArea(Point *P,Re n){
    LD ans=0;
    for(Re i=1;i<=n;++i)ans+=Cro(P[i],P[i<n?i+1:1]);
    return ans/2.0;
}
struct Line{
    Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
    inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}
}Q[N<<1];
inline int judge(Point a,Line L){return dcmp(Cro(a-L.a,L.b-L.a))>0;}//判断点a是否在L右边
inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}
inline int halfcut(Line *L,Re n,Point *P){
    sort(L+1,L+n+1);Re m=0;
    for(Re i=1;i<=n;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++m]=L[i];
    Re h=1,t=0;
    for(Re i=1;i<=m;++i){
        while(h<t&&judge(cross(Q[t],Q[t-1]),L[i]))--t;
        while(h<t&&judge(cross(Q[h],Q[h+1]),L[i]))++h;
        Q[++t]=L[i];
    }
    while(h<t&&judge(cross(Q[t],Q[t-1]),Q[h]))--t;
    while(h<t&&judge(cross(Q[h],Q[h+1]),Q[t]))++h;
    m=0;
    for(Re i=h;i<=t;++i)P[++m]=cross(Q[i],Q[i<t?i+1:h]);
    return m;
}
int n,m;Point P[N],PP[N<<1];Line L[N<<1];
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)P[i].in();P[n+1]=P[1];
    for(Re i=2;i<=n;++i){
        Point tmp=P[1]-P[2]-P[i]+P[i+1];
        LD a=tmp.y,b=-tmp.x,c=Cro(P[1],P[2])-Cro(P[i],P[i+1]);//ax+by+c<=0
        if(!dcmp(a)&&!dcmp(b)){
            if(dcmp(c)<=0)continue;
            else{puts("0");return 0;}
        }
        if(!dcmp(a)){//by+c<=0
            if(b>0)L[++m]=Line(Point(1,-c/b),Point(0,-c/b));//y<=-c/b
            else L[++m]=Line(Point(0,-c/b),Point(1,-c/b));//y>=-c/b
        }
        else if(!dcmp(b)){//ax+c<=0
            if(a>0)L[++m]=Line(Point(-c/a,0),Point(-c/a,1));//x<=-c/a
            else L[++m]=Line(Point(-c/a,1),Point(-c/a,0));//x>=-c/a
        }
        else if(b>0)L[++m]=Line(Point(1,-a/b-c/b),Point(0,-c/b));//y<=-a/b*x-c/b
        else L[++m]=Line(Point(0,-c/b),Point(1,-a/b-c/b));//y>=-a/b*x-c/b
    }
    for(Re i=1;i<=n;++i)L[++m]=Line(P[i],P[i+1]);
    Re cnt=halfcut(L,m,PP);
    printf("%.4lf\n",PolyArea(PP,cnt)/PolyArea(P,n));
}

【Day2 T1】小凸玩密室

传送门：小凸玩密室 \(\text{[P4253]}\) \(\text{[Bzoj4446]}\)

【题目描述】

给出一颗 \(n\) \((n\leqslant 2*10^5)\) 个点的完全二叉树，其中点 \(i\) 的权值为 \(A[i]\) 。现要给所有点染色，染第一个点不需要花费，在这之后每染一个新点 \(y\)，设上次染色的点为 \(x\)，则染 \(y\) 的花费为 \(dis(x,y)*A_y\) 。要求在任意时刻已被染色的点必须连通，且每次给任意一个点 \(x\) 染色后，必须要把 \(x\) 的子树内所有点都染完后才能染 \(x\) 子树外的点。

【分析】

毒瘤树形 \(dp\) 。

设 \(pl\) 为 \(x\) 的左儿子，\(pr\) 为 \(x\) 的右儿子，\(\{son_i\}\) 为点 \(i\) 子树内的点组成的集合。

用 \(f[x][y]\) 表示从 \(x\) 出发，染完 \(x\) 的子树后到达 \(y\) 点的最小花费，则有 \((to\) 为点 \(x\) 子树中的叶节点或者缺了一个儿子的点 \()\)：

\[f[x][y]=\min\begin{cases} dis(x,pr)*A[pr]+f[pr][to]+dis(to,pl)*A[pl]+f[pl][y], y\in \{son_{pl}\}\\ dis(x,pl)*A[pl]+f[pl][to]+dis(to,pr)*A[pr]+f[pr][y], y\in \{son_{pr}\} \end{cases} \]

考虑把第一个式子里的 \(dis(to,pl)\) 展开，变成 \(dis(to,x)+dis(x,pl)\)，得到 \(f[x][y]=dis(x,pr)*A[pr]+dis(x,pl)*A[pl]\) \(+\min\{f[pr][to]+dis(to,x)*A[pl]+f[pl][y]\}\)，发现 \(f[pr][to]+dis(to,x)*A[pl]\) 可以提前扫描一遍预处理得出，于是复杂度便降到了 \(O(\sum_{i=1}^{n}\text{点}\ i\ \text{子树内缺儿子的点的个数})=O(n\log n)\) 。第二个式子同理。

由于无法确定开始染色的第一个点，所以还要再设一个方程，用 \(g[x][y]\) 表示以 \(x\) 子树内的任意一点作为起点，最后到达 \(y\) 所需的最小花费，则有：

\[g[x][y]=\min\begin{cases} f[x][y]\\ g[pr][to]+dis(to,x)*A[x]+dis(x,pl)*A[pl]+f[pl][y], y\in \{son_{pl}\}\\ g[pl][to]+dis(to,x)*A[x]+dis(x,pr)*A[pr]+f[pr][y], y\in \{son_{pr}\} \end{cases} \]

发现下面那两个柿子也可以用类似上面 \(f\) 的做法进行优化。

由于完全二叉树良好的性质，复杂度均为 \(O(n\log n)\) 。

【Code】

一开始用了 \(map\) 存状态（好写一点），\(loj\) 轻松水过，洛谷 \(MLE+TLE\)，只好换成 \(vector\)，结果又调了好长时间。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define LL long long
#define Re register LL
using namespace std;
const LL N=2e5+3,inf=1e18;
LL n,A[N],B[N][2],deep[N];vector<LL>f[N],g[N],son[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
#define pl (x<<1)
#define pr (x<<1|1)
inline int dis(Re x,Re y){return x>y?deep[x]-deep[y]:deep[y]-deep[x];}
inline void dfs(Re x){
    deep[x]=deep[x>>1]+B[x>>1][x&1];
    if(!B[x][0]){//叶子节点
        Re p=x;while(p)son[p].push_back(x),f[p].push_back(0),g[p].push_back(0),p>>=1;
    }
    else if(!B[x][1]){//只有左儿子
        dfs(pl);
        Re p=x;while(p)son[p].push_back(x),f[p].push_back(0),g[p].push_back(0),p>>=1;
        f[x][0]=dis(x,pl)*A[pl],g[x][0]=dis(x,pl)*A[pl];//son[x][0]: pl
        f[x][1]=inf,g[x][1]=dis(x,pl)*A[x];//son[x][1]: x
    }
    else{//有两个儿子
        dfs(pl);Re cut=son[x].size();dfs(pr);Re f0=inf,f1=inf,g0=inf,g1=inf;
        for(Re i=0,to,m=son[x].size();i<m;++i){
            to=son[x][i];
            if(i<cut){//to在左子树
                f0=min(f0,f[pl][i]+dis(to,x)*A[pr]);
                g0=min(g0,g[pl][i]+dis(to,x)*A[x]);
            }
            else{//to在右子树
                f1=min(f1,f[pr][i-cut]+dis(to,x)*A[pl]);
                g1=min(g1,g[pr][i-cut]+dis(to,x)*A[x]);
            }
        }
        Re tmp=dis(x,pl)*A[pl]+dis(x,pr)*A[pr];
        for(Re i=0,to,m=son[x].size();i<m;++i){
            to=son[x][i];
            if(i<cut){//to在左子树
                f[x][i]=tmp+f[pl][i]+f1;
                g[x][i]=min(f[x][i],dis(x,pl)*A[pl]+f[pl][i]+g1);
            }
            else{//to在右子树
                f[x][i]=tmp+f[pr][i-cut]+f0;
                g[x][i]=min(f[x][i],dis(x,pr)*A[pr]+f[pr][i-cut]+g0);
            }
        }
    }
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(A[i]);
    for(Re i=1;i<n;++i)in(B[i+1>>1][(i&1)^1]);
    dfs(1);Re ans=inf;
    for(Re i=0,m=son[1].size();i<m;++i)ans=min(ans,g[1][i]);
    printf("%lld\n",ans);
}

【Day2 T2】小凸解密码

传送门：小凸解密码 \(\text{[P5226]}\) \(\text{[Bzoj4447]}\)

【题目描述】

给出一个大小为 \(n\) \((n\leqslant 2*10^5)\) 的环，环上每个点有两种权值 \((x,ch)\)，其中 \(x\in[0,9]\)，\(ch\) 为 '\(+\)' 或 '\(*\)'。

有若干次操作，每次操作有两种情况：

\(1\ x\ y\ ch:\) 将第 \(x+1\) 个点修改为 \((y,ch)\)
\(1\ x:\) 从 \(x+1\) 开始，按照顺时针将两种权值分别记录到 \(A\) 数组和 \(C\) 中，则 \(B_i=\begin{cases}A_1\ (i=1)\\(A_i+A_{i-1})\%10\ (i>1,C_i=‘+’)\\ (A_i*A_{i-1})\%10\ (i>1,C_i=‘*’)\end{cases}\)，然后将 \(B\) 数组连城成一个环，在这个环上会有一些 \(0\) 连在一起，将这些连在一起的 \(0\) 称为零区间，求距离 \(B_1\) 最远的零区间，并输出这个距离（零区间和 \(B_1\) 的距离定义为：零区间内所有 \(0\) 到 \(B_1\) 距离中的最小值）。

【分析】

暴力二分+线段树瞎搞。

首先要把环复制一下变为链（一年考两个环，不愧为毒瘤 \(OI\)），考虑用线段树维护 \(B\) 数组，每次 \(1\) 操作最多只会影响到四个位置 \((B_x,B_{x+1},B_{x+n},B_{x+n+1})\)，暴力修改即可。

考虑解决询问，求最小的最大明显可以二分，设当前的二分值为 \(mid\)，则需要检查 \([x+mid,x+n-1-mid+1]\) 里是否有一段全为 \(0\) 的子区间（需要满足该子区间左右两边均不为 \(0\)），但这个东西很不好求，考虑把询问区间分别向左右两边扩大一格得到 \([ql,qr]\)，然后查询 \([ql,qr]\) 内是否存在左端点大于 \(ql\) 且右端点小于 \(qr\) 的全 \(0\) 子区间即可。

时间复杂度：\(O(n\log^2 n)\) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,x,y,T,op,A[N<<1];char ch,type[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int calc(Re i){return i?(type[i]=='+'?(A[i]+A[i-1])%10:A[i]*A[i-1]%10):A[i];}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{
        int S;bool l,r,ans;
        inline QAQ operator+(const QAQ &R){
            QAQ p;p.S=S+R.S,p.l=l,p.r=R.r;
            p.ans=ans||R.ans||(S&&R.S&&(!r||!R.l));
            return p;
        }
    }tr[N<<3];
    inline void updata(Re p,Re x,Re v=-1){
        tr[p].ans=0,tr[p].l=tr[p].r=tr[p].S=((v==-1?calc(x):v)>0);
    }
    inline void build(Re p,Re L,Re R){
        if(L==R){updata(p,L);return;}
        build(pl,L,mid),build(pr,mid+1,R);
        tr[p]=tr[pl]+tr[pr];
    }
    inline void refresh(Re p,Re L,Re R,Re x){
        if(L==R){updata(p,L);if(x<=n)refresh(1,1,n<<1,x+n);return;}
        if(x<=mid)refresh(pl,L,mid,x);
        else refresh(pr,mid+1,R,x);
        tr[p]=tr[pl]+tr[pr];
    }
    inline void change(Re p,Re L,Re R,Re x,Re v){
        if(L==R){updata(p,x,v);return;}
        if(x<=mid)change(pl,L,mid,x,v);
        else change(pr,mid+1,R,x,v);
        tr[p]=tr[pl]+tr[pr];
    }
    inline QAQ ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p];
        if(r<=mid)return ask(pl,L,mid,l,r);
        else if(l>mid)return ask(pr,mid+1,R,l,r);
        else return ask(pl,L,mid,l,r)+ask(pr,mid+1,R,l,r);
    }
}T1;
int main(){
//    freopen("456.txt","r",stdin);
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]),scanf("%c",&type[i]),A[i+n]=A[i],type[i+n]=type[i];
    T1.build(1,1,n<<1);
    while(T--){
        in(op),in(x),++x;
        if(op<2){
            in(y),scanf("%c",&ch),A[x]=A[x+n]=y,type[x]=type[x+n]=ch,
            T1.refresh(1,1,n<<1,x),T1.refresh(1,1,n<<1,x+1);
        }
        else{
            Re L=x,R=x+n-1,ans=-1;
            if(!A[L])ans=0;
            T1.change(1,1,n<<1,L,A[L]);
            Re l=1,r=(n+1)/2;
            while(l<=r){
                Re Mid=l+r>>1;
                if(T1.ask(1,1,n<<1,L+Mid-1,R-Mid+1+1).ans)ans=Mid,l=Mid+1;
                else r=Mid-1;
            }
            T1.change(1,1,n<<1,L,calc(L));
            printf("%d\n",ans);
        }
    }
}

【Day2 T3】情报传递

传送门：情报传递 \(\text{[P4216]}\) \(\text{[Bzoj4448]}\)

【题目描述】

给出一颗 \(n\) \((n\leqslant 2*10^5)\) 个点的有根树，有若干个操作，操作种类如下：

\(1\ x\ y\ c:\) 设当前为第 \(i\) 的操作，分别查询从 \(x\) 到 \(y\) 的链上点的个数、满足 \(i-st_j>c\) 的 \(j\) 的个数
\(2\ x:\) 设当前为第 \(i\) 的操作，设置 \(st_x=i\)

【分析】

小学生级别的主席树大水题。

询问第一个子问题直接求 \(lca\) 用各点深度相减即可，第二个子问题可转化为查询满足 \(st_j\leqslant i-c-1\) 的 \(j\) 的个数，直接在主席树上差分搞即可。

可以发现没必要写带修的树套树版本，把所有操作 \(2\) 全部拿出来建好树，然后再去挨个处理询问，这样做是不影响正确性的（数据里没有出现同一个点多次进行操作 \(2\) 的情况）。

时间复杂度：\(O(n\log n)\) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,logN=18,inf=2e9;
int n,x,y,z,o,m,T,op,rt,A[N],st[N],fa[N],head[N],deep[N];
struct QAQ{int to,next;}a[N];
struct Query{int x,y,c,t;}Q[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
    int ant[N][20];
    inline void dfs(Re x){
        deep[x]=deep[ant[x][0]=fa[x]]+1;
        for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
        for(Re i=head[x];i;i=a[i].next)dfs(a[i].to);
    }
    inline int lca(Re x,Re y){
        if(deep[x]<deep[y])swap(x,y);
        for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
        if(x==y)return x;
        for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
        return ant[x][0];
    }
}T1;
int pt[N];
struct Segment_Tree{
    #define pl (tr[p].lp)
    #define pr (tr[p].rp)
    #define mid ((L+R)>>1)
    int O;
    struct QAQ{int S,lp,rp;}tr[N*logN<<2];
    inline void creat(Re &p,Re q,Re L,Re R,Re x){
        tr[p=++O]=tr[q],++tr[p].S;
        if(L==R)return;
        if(x<=mid)creat(pl,tr[q].lp,L,mid,x);
        else creat(pr,tr[q].rp,mid+1,R,x);
    }
    inline int ask(Re p,Re q,Re f1,Re f2,Re L,Re R,Re l,Re r){
        if(!p&&!q&&!f1&&!f2)return 0;
        if(l<=L&&R<=r)return tr[p].S+tr[q].S-tr[f1].S-tr[f2].S;
        Re ans=0;
        if(l<=mid)ans+=ask(pl,tr[q].lp,tr[f1].lp,tr[f2].lp,L,mid,l,r);
        if(r>mid)ans+=ask(pr,tr[q].rp,tr[f1].rp,tr[f2].rp,mid+1,R,l,r);
        return ans;
    }
}TR;
inline void dfs(Re x){
    TR.creat(pt[x],pt[fa[x]],1,T,st[x]);
    for(Re i=head[x];i;i=a[i].next)dfs(a[i].to);
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i){
        in(fa[i]);
        if(fa[i])add(fa[i],i);
        else rt=i;
    }
    in(T),T1.dfs(rt);
    for(Re i=1;i<=n;++i)st[i]=T;//st要初始化为一个极大值(设到T就够了)
    for(Re i=1;i<=T;++i){
        in(op);
        if(op>1)in(x),st[x]=i;
        else in(Q[++m].x),in(Q[m].y),in(Q[m].c),Q[m].t=i;
    }
    dfs(rt);
    for(Re i=1;i<=m;++i){
        Re lca=T1.lca(Q[i].x,Q[i].y);
        printf("%d %d\n",deep[Q[i].x]+deep[Q[i].y]-deep[lca]-deep[fa[lca]],TR.ask(pt[Q[i].x],pt[Q[i].y],pt[lca],pt[fa[lca]],1,T,1,Q[i].t-Q[i].c-1));
    }
}

码农公寓

【题解】毒瘤 OI 刷题汇总 [SCOI2015]

【Day1 T1】小凸玩矩阵

【题目描述】

【分析】

【Code】

【Day1 T2】国旗计划

【题目描述】

【分析】

【Code】

【Day1 T3】小凸想跑步

【题目描述】

【分析】

【Code】

【Day2 T1】小凸玩密室

【题目描述】

【分析】

【Code】

【Day2 T2】小凸解密码

【题目描述】

【分析】

【Code】

【Day2 T3】情报传递

【题目描述】

【分析】

【Code】

相关文章