蒟蒻讲水题

讲义

目录

• 蒟蒻讲水题
  • 1.[BZOJ 2959] 长跑
    • 思路
    • 代码
  • 2.[UOJ 164] V
    • 思路
    • 代码
  • 3.[BZOJ 2956] 模积和
    • 思路
    • 代码

1.[BZOJ 2959] 长跑

题目大意：
给定$n$个点，$1 \leq n \leq 1.5 \times 10^5$，支持加边操作，询问两点间每条边只能沿一个固定方向走所经过的路径上的点的点权和最大值（询问和操作总次数$m$满足$m \leq 5n$）。

思路

• 考虑边双是指至少有两条不经过相同边的路径的两点；
• 很容易知道，可以经过的所有点是这两个点的路径上的点及路径所连接的边双上的点；
• 又因为边双缩点后是一个森林，所以考虑用并查集维护点所在的边双；
• 由于缩点是一个动态操作，且是对森林的操作，我们考虑使用LCT维护；
• 易证，单纯缩点的复杂度是均摊$O(1)$的（最多缩$n$次，平均每次缩一个），用LCT维护的话就是均摊$O( \log n)$；
• 查询也很简单，就是缩点后树上两点间路径上的点的点权和，单次操作复杂度也是$O(\log n)$；
• 综上，总复杂度就是$O(m \log n)$。

注意，由于LCT**常数巨大，两点连通性应用另一个并查集**维护，而不是LCT的find_rt()不然会T。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
using std::swap;
using std::queue;
const int MAXN=1.5e5+5;
int tmp[MAXN];
struct node{
    int s[2],fa,w,sum;
    bool rev;
};
class UFset{
    private:
        int anc[MAXN];
    public:
        void init(int n){
            for(int i=1;i<=n;++i)
                anc[i]=i;
        }
        int find(int x){
            return anc[x]==x ? x:anc[x]=find(anc[x]);
        }
        void uni(int x,int y){anc[find(x)]=find(y);}
};
class LCT{
    private:
        bool vis[MAXN];
        node d[MAXN];
        UFset ufs,cnn;
        void upd(int u){
            d[u].sum=d[d[u].s[0]].sum+d[d[u].s[1]].sum+d[u].w;
        }
        void push_d(int u){
            if(!d[u].rev) return;
            d[d[u].s[0]].rev^=true;
            d[d[u].s[1]].rev^=true;
            swap(d[u].s[0],d[u].s[1]);
            d[u].rev=false;
        }
        bool is_rt(int u){
            int ufa=d[u].fa;
            return d[ufa].s[0]!=u && d[ufa].s[1]!=u;
        }
        void rot(int u){
            int ufa=d[u].fa;
            push_d(ufa),push_d(u);
            bool lr=d[ufa].s[1]==u;
            d[u].fa=d[ufa].fa;
            if(!is_rt(ufa))
                d[d[u].fa].s[d[d[u].fa].s[1]==ufa]=u;
            d[ufa].s[lr]=d[u].s[lr^1];
            d[d[ufa].s[lr]].fa=ufa;
            d[u].s[lr^1]=ufa;
            d[ufa].fa=u;
            upd(ufa),upd(u);
        }
        void spl(int u){
            push_d(u);
            int &ufa=d[u].fa,&ugfa=d[ufa].fa;
            while(!is_rt(u)){
                if(!is_rt(ufa)){
                    if((d[ufa].s[0]==u)!=(d[ugfa].s[0]==ufa))
                        rot(u);
                    else rot(ufa);
                }
                rot(u);
            }
        }
        void acc(int u){
            for(int v=0;u;v=u,u=ufs.find(d[u].fa)){
                spl(u);
                d[u].s[1]=v;
                d[v].fa=u;
                upd(u);
            }
        }
        void be_rt(int u){
            acc(u),spl(u);
            d[u].rev^=true;
        }
        void spl_mge(int u,int v){
            be_rt(u),acc(v),spl(u);
        }
        void linkE(int u,int v){
            be_rt(u),d[u].fa=v;
            cnn.uni(u,v);
        }
        void mge_node(int u,int v){
            static queue<int> q;
            spl_mge(u,v);
            q.push(u);
            int now;
            while(q.size()){
                now=q.front();
                q.pop();
                ufs.uni(now,u);
                if(d[now].s[0])
                    q.push(d[now].s[0]);
                if(d[now].s[1])
                    q.push(d[now].s[1]);
                d[now].fa=d[now].s[0]=d[now].s[1]=0;
            }
            d[u].w=d[u].sum;
        }
    public:
        void init(int n){
            ufs.init(n),cnn.init(n);
            for(int i=1;i<=n;++i)
                d[i].sum=d[i].w=tmp[i];
        }
        void link(int u,int v){
            u=ufs.find(u),v=ufs.find(v);
            if(u==v) return;
            else if(cnn.find(u)!=cnn.find(v))
                linkE(u,v);
            else mge_node(u,v);
        }
        void mdf(int u,int w){
            int now_u=ufs.find(u);
            be_rt(now_u);
            d[now_u].w+=w-tmp[u];
            tmp[u]=w;
            upd(now_u);
        }
        int qry(int u,int v){
            u=ufs.find(u),v=ufs.find(v);
            if(u==v) return d[u].w;
            else if(cnn.find(u)!=cnn.find(v))
                return -1;
            spl_mge(u,v);
            return d[u].sum;
        }
}T;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&tmp[i]);
    T.init(n);
    for(int i=1,p,a,b;i<=m;++i){
        scanf("%d%d%d",&p,&a,&b);
        if(p==1) T.link(a,b);
        else if(p==2) T.mdf(a,b);
        else printf("%d\n",T.qry(a,b));
    }
    return 0;
}

2.[UOJ 164] V

题目大意：
给定一个$n$个元素的序列$a$，$1 \leq n \leq 5 \times 10^5$，要求支持5种操作（次数$m$满足$1 \leq m \leq 5 \times 10^5$）：
1.把$a_l$~$a_r$每个元素加上$x$；
2.把$a_l$~$a_r$每个元素赋值为$x$；
3.把$a_l$~$a_r$每个元素赋值为$\max(a_i-x,0)$；
4.询问当前$a_i$的值；
5.询问$a_i$的历史最大值.

思路

• 乍一看，线段树裸题，但仔细一想就gg了；
• 因为前3个操作的$tag$没法弄，如果不想办法合并，不是T就是M；
• 不过仔细观察，就可以发现，其实$tag$是可以合并的；
• 考虑一个二元组$(p,q)$表示对操作$\max(a_i+p,q)$；
• 则初始时$tag$为$(0,-\inf)$，三个操作分别可以表示为$(x,-\inf),(-\inf,x),(-x,0)$；
• 现在考虑两个$tag$，分别为$(p_1,q_1),(p_2,q_2)$，那么如何合并？
• 上面的操作等价为：$\max(\max(a_i+p_1,q_1)+p_2,q_2)=\max(a_i+p_1+p_2,q_1+p_2,q_2)$
• 我们可以用二元组表示化简为$\max(p_1+p_2,\max(q_1+p_2,q_2))$；
• 现在考虑历史最大值，显然不能像以前一样每个点记录一下了，我们需要考虑多存一个历史标记，单独合并，查询时算一下就好了；
• 设$f_m(a_i)$为$m$次操作后$a_i$的历史最大值；
• 则每次操作同之前的二元组相同，但是合并方式不同；
• 具体是这样$(p_1,q_1),(p_2,q_2)\to(\max(p_1,p_2),\max(q_1,q_2))$；
• 这样，写好push_down()函数，就可以水过了。。。

注意：push_down()不能将叶节点$tag$下传，因为我们是用$tag$计算询问，不能把$tag$推没了...而且其中有一步和$-\inf$取$\max$，是防止$\inf+(-\inf)$溢出！

代码

#include <cstdio>
#include <algorithm>
#include <utility>
#include <climits>
using std::max;
using std::pair;
const int MAXN=5e5+5;
const long long INF=1e18;
int tmp[MAXN];
struct option{
    pair<long long,long long> his,now;
    void clear(){
        now=pair<long long,long long>(0,-INF);
        his=pair<long long,long long>(0,-INF);
    }
    void mge(const option &a){
        his.first=max(his.first,a.his.first+now.first);
        his.second=max(his.second,max(a.his.first+now.second,a.his.second));
        now.first=max(now.first+a.now.first,-INF);
        now.second=max(now.second+a.now.first,a.now.second);
    }
};
struct node{
    int ls,rs,lp,rp,w;
    option tag;
};
class segT{
    private:
        node d[MAXN<<2];
        void push_d(int u){
            d[d[u].ls].tag.mge(d[u].tag);
            d[d[u].rs].tag.mge(d[u].tag);
            d[u].tag.clear();
        }
        void build(int u,int l,int r){
            static int cnt=1;
            d[u].lp=l,d[u].rp=r;
            d[u].tag.clear();
            if(l==r){
                d[u].w=tmp[l];
                return;
            }
            int mid=l+r>>1;
            d[u].ls=++cnt;
            build(cnt,l,mid);
            d[u].rs=++cnt;
            build(cnt,mid+1,r);
        }
        void mdf(int u,int l,int r,const option &k){
            if(l<=d[u].lp && d[u].rp<=r){
                d[u].tag.mge(k);
                return;
            }
            push_d(u);
            int mid=d[u].lp+d[u].rp>>1;
            if(l<=mid) mdf(d[u].ls,l,r,k);
            if(r>mid) mdf(d[u].rs,l,r,k);
        }
        long long qry(int u,int pos,bool type){
            if(d[u].lp==d[u].rp){
                const pair<long long,long long> &tmp= type ? d[u].tag.now:d[u].tag.his;
                return max(d[u].w+tmp.first,tmp.second);
            }
            push_d(u);
            int mid=d[u].lp+d[u].rp>>1;
            if(pos<=mid) return qry(d[u].ls,pos,type);
            else return qry(d[u].rs,pos,type);
        }
    public:
        void build(int n){build(1,1,n);}
        void mdf(int l,int r,option &k){mdf(1,l,r,k);}
        long long qry(int pos,bool type){return qry(1,pos,type);}
}T;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&tmp[i]);
    T.build(n);
    option opt;
    for(int i=1,t,l,r,x;i<=m;++i){
        scanf("%d",&t);
        if(t<=3){
            scanf("%d%d%d",&l,&r,&x);
            if(t==1){
                opt.now=pair<long long,long long>(x,-INF);
                opt.his=pair<long long,long long>(x,-INF);
            }
            else if(t==2){
                opt.now=pair<long long,long long>(-x,0);
                opt.his=pair<long long,long long>(-x,0);
            }
            else{
                opt.now=pair<long long,long long>(-INF,x);
                opt.his=pair<long long,long long>(-INF,x);
            }
            T.mdf(l,r,opt);
        }
        else{
            scanf("%d",&x);
            printf("%lld\n",T.qry(x,t==4));
        }
    }
    return 0;
}

3.[BZOJ 2956] 模积和

题目大意：
求$\sum_{i=1}^n \sum_{j=1,j \neq i}^m(n \mod i)\times(m \mod j)\pmod{19940417},1 \leq n,m \leq 10^9$.

思路

• 数据显然要$O(\sqrt n)$做法，又因为取模，我们考虑将取模拆开，弄成分段的情况：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^n\sum_{j=1,j \neq i}^m(n-i \times\lfloor\frac{n}{i}\rfloor)\times(m-j \times\lfloor\frac{m}{j}\rfloor) \\ &=& \sum_{i=1}^n(n-i \times\lfloor\frac{n}{i}\rfloor)\times\sum_{i=1}^m(m-i \times\lfloor\frac{m}{i}\rfloor)-\sum_{i=1}^{\min(n,m)}(n-i \times\lfloor\frac{n}{i}\rfloor)\times(m-i \times\lfloor\frac{m}{i}\rfloor) \\ &=& (n^2-\sum_{i=1}^n i \times\lfloor\frac{n}{i}\rfloor)\times(m^2-\sum_{i=1}^m i \times\lfloor\frac{m}{i}\rfloor)-\sum_{i=1}^{\min(n,m)}(n-i \times\lfloor\frac{n}{i}\rfloor)\times(m-i \times\lfloor\frac{m}{i}\rfloor) \\ &=& (n^2-\sum_{i=1}^n i \times\lfloor\frac{n}{i}\rfloor)\times(m^2-\sum_{i=1}^m i \times\lfloor\frac{m}{i}\rfloor)-\min(n,m)\times n \times m+m \times\sum_{i=1}^{ \min(n,m)}i \times\lfloor\frac{n}{i}\rfloor+n \times\sum_{i=1}^{\min(n,m)}i \times\lfloor\frac{m}{i}\rfloor-\sum_{i=1}^{\min(n,m)}i^2 \times\lfloor\frac{n}{i} \rfloor\times\lfloor\frac{m}{i}\rfloor \end{eqnarray*}$$
• 之后就愉快的用分块秒了，但是注意有一步要变为乘上逆元，请自行思考。

代码

#include <cstdio>
#include <algorithm>
using std::min;
const int P=19940417,inv_6=3323403;
int n,m,ans;
inline int blk_solve(int x,int y){
    int ret=0;
    for(int l=1,r;l<=y;l=r+1){
        r=min(x/(x/l),y);
        ret=(ret+(long long)((long long)(l+r)*(r-l+1)>>1)%P*(x/l)%P)%P;
    }
    return ret;
}
inline long long sqr_sum(int r){
    return (long long)r*(r+1)%P*(r<<1|1)%P*inv_6%P;
}
int main(){
    scanf("%d%d",&n,&m);
    ans=((long long)n*n%P-blk_solve(n,n)+P)%P;
    ans=(long long)ans*(((long long)m*m%P-blk_solve(m,m)+P)%P)%P;
    ans=(ans-(long long)min(n,m)*n%P*m%P+P)%P;
    ans=(ans+(long long)n*blk_solve(m,min(n,m))%P)%P;
    ans=(ans+(long long)m*blk_solve(n,min(n,m))%P)%P;
    for(int l=1,r;l<=min(n,m);l=r+1){
        r=min(min(n/(n/l),m/(m/l)),min(n,m));
        ans=(ans-(long long)(n/l)%P*(m/l)%P*(sqr_sum(r)-sqr_sum(l-1)+P)%P+P)%P;
    }
    printf("%d",ans);
    return 0;
}

题太水了，巨佬们不要D我orz...