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

【题解】毒瘤 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));
    }
}

上一篇:学习ZYNQ之FPGA的第二天(开发板资源初探)


下一篇:pl/sql