• Time limit 10000 ms
• Memory limit 265216 kB
• OS Linux

吐槽

又浪费一个下午……区间乘-1之后，最大值和最小值更新有坑。新的最大值是原来最小值乘-1，新的最小值是原来最大值乘-1。

没脸见人了

树链剖分，但这题的权值在边上不在点上，那我们只需要在dfs过程中把边权搞到下方的点上，然后两点间各种操作时，不对两点LCA进行操作就好(见代码里一串/)

听说LCT处理这个更擅长，留坑

源代码

#include
    
     #include
     
      #include
      
       #include
       
        const int MAXN=2e4+5;int n,q;struct Edge{    int nxt,to,w,id;}e[MAXN<<1];int head[MAXN],cnt=1;inline void add(int u,int v,int w,int id){    e[cnt]={head[u],v,w,id};    head[u]=cnt++;    e[cnt]={head[v],u,w,id};    head[v]=cnt++;}int bridge[MAXN];//用桥的id查询点struct Tree{    int w;    int fa,dep,sz,wson;    int id,top;}t[MAXN];void dfs1(int u,int fa,int eid){    t[u].w=e[eid].w;    bridge[e[eid].id]=u;    t[u].fa=fa;    t[u].dep=t[t[u].fa].dep+1;    t[u].sz=1;    int mxson=-1;    for(int i=head[u];i;i=e[i].nxt)    {        int v=e[i].to;        if(fa==v) continue;        dfs1(v,u,i);        int temp=t[v].sz;        if(temp>mxson)        {            t[u].wson=v;            mxson=temp;        }        t[u].sz+=temp;    }}int a[MAXN],id=1;void dfs2(int u,int top){    t[u].top=top;    t[u].id=id;    a[id]=t[u].w;    id++;    if(t[u].sz==1) return;    dfs2(t[u].wson,top);    for(int i=head[u];i;i=e[i].nxt)    {        int v=e[i].to;        if(v==t[u].wson||v==t[u].fa) continue;        dfs2(v,v);    }}struct Segtree{    int sum;    int mx;    int mn;    bool lazy;//乘-1的}s[MAXN<<2];inline void pushup(int x){    s[x].sum=s[x<<1].sum+s[x<<1|1].sum;    s[x].mx=std::max(s[x<<1].mx,s[x<<1|1].mx);    s[x].mn=std::min(s[x<<1].mn,s[x<<1|1].mn);}void build(int x,int l,int r){    if(l==r)    {        s[x]={a[l],a[l],a[l],0};        return;    }    int mid=l+r>>1;    build(x<<1,l,mid);    build(x<<1|1,mid+1,r);    pushup(x);}inline void pushdown(int x){    if(!s[x].lazy) return;    s[x<<1].lazy=!s[x<<1].lazy;    int temp=s[x<<1].mx;    s[x<<1].mx=-s[x<<1].mn;    s[x<<1].mn=-temp;    s[x<<1].sum*=-1;    s[x<<1|1].lazy=!s[x<<1|1].lazy;    temp=s[x<<1|1].mx;    s[x<<1|1].mx=-s[x<<1|1].mn;    s[x<<1|1].mn=-temp;    s[x<<1|1].sum*=-1;    s[x].lazy=0;}void mul(int x,int l,int r,int ql,int qr)//区间乘-1{    if(ql<=l&&r<=qr)    {        s[x].lazy=!s[x].lazy;        int temp=s[x].mx;        s[x].mx=-s[x].mn;        s[x].mn=-temp;        s[x].sum*=-1;        return;    }    pushdown(x);    int mid=l+r>>1;    if(ql<=mid) mul(x<<1,l,mid,ql,qr);    if(qr>mid) mul(x<<1|1,mid+1,r,ql,qr);    pushup(x);}void change(int x,int l,int r,int pos,int k){    if(l==r)    {        s[x].mn=k;        s[x].mx=k;        s[x].sum=k;        return;    }    pushdown(x);    int mid=l+r>>1;    if(pos<=mid) change(x<<1,l,mid,pos,k);    else change(x<<1|1,mid+1,r,pos,k);    pushup(x);}int quesum(int x,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return s[x].sum;    int mid=l+r>>1;    int ans=0;    pushdown(x);    if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);    if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);    return ans;}int quemx(int x,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return s[x].mx;    int mid=l+r>>1;    int ans=-99999999;    pushdown(x);    if(ql<=mid) ans=std::max(quemx(x<<1,l,mid,ql,qr),ans);    if(qr>mid) ans=std::max(quemx(x<<1|1,mid+1,r,ql,qr),ans);    return ans;}int quemn(int x,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return s[x].mn;    int mid=l+r>>1;    int ans=99999999;    pushdown(x);    if(ql<=mid) ans=std::min(quemn(x<<1,l,mid,ql,qr),ans);    if(qr>mid) ans=std::min(quemn(x<<1|1,mid+1,r,ql,qr),ans);    return ans;}void optn(int x,int y){    while(t[x].top!=t[y].top)    {        if(t[t[x].top].dep
        
         t[y].id) std::swap(x,y);    mul(1,1,n,t[x].id+1,t[y].id);///}int optsum(int x,int y){    int ans=0;    while(t[x].top!=t[y].top)    {        if(t[t[x].top].dep
         
          t[y].id) std::swap(x,y); ans+=quesum(1,1,n,t[x].id+1,t[y].id); return ans;}int optmx(int x,int y){ int ans=-99999999; while(t[x].top!=t[y].top) { if(t[t[x].top].dep
          
           t[y].id) std::swap(x,y); ans=std::max(ans,quemx(1,1,n,t[x].id+1,t[y].id)); return ans;}int optmn(int x,int y){ int ans=99999999; while(t[x].top!=t[y].top) { if(t[t[x].top].dep
           
            t[y].id) std::swap(x,y); ans=std::min(ans,quemn(1,1,n,t[x].id+1,t[y].id)); return ans;}int main(){ //freopen("test.in","r",stdin); scanf("%d",&n); for(int i=1,u,v,w;i