题目分析

神仙题（确信）

首先，$j-a _ i$和 $a _ i-j$互为相反数，若其中最小值为 $b _ i$，则一个为 $b _ i$一个为 $m-b _ i$。（以下运算均在模 $m$意义下进行）

$j-a _ i = b _ i$即 $j= a _ i + b _ i$

$a _ i – j = b _ i$即 $j= a _ i – b _ i$

$j-a _ i = -b _ i$即 $j= a _ i – b _ i$

$a _ i – j = -b _ i$即 $j= a _ i + b _ i$

所以 $j$只有一种或两种取值。

由于原图有完美匹配，根据霍尔定理，对于任意一个妹子的子集 $S$，与其有边相连的男生集合 $Y _ S$都满足 $|Y _ S| \geq |S|$。所以若我们将一个妹子可以找的两个男生之间连一条边（若只能找一个男生，就连个自环），那么对于任意一个男生子集 $T$，在这个子集中的边数都小于等于点数，所以任意一个连通块，要么是树，要么是基环树。

假如妹子 $i$选择男生 $a$获得愉悦度 $w _ a$，选择男生 $b$获得愉悦度 $w _ b$，则连边 $(b,a,w _ a)$和 $(a,b,w _ b)$，这两条边只能选一条也必须选一条，并且每个男生点的入度都最多为 $1$。

对于树，一定是以某个点为根的一棵外向树形图。所以用 dfs 序为下标建立线段树，每个位置维护以这个点为根的外向树贡献是多少，改一条边权值时维护一下即可。

对于基环树，环外的树一定都是外向的，有些边是必选有些是必不选。环的话，存一下环两个方向的贡献，修改时维护。

然后我们都知道，基环树的题目思路听起来简单，写死人。

实现上，我是记录了一条边属于哪一种边，分别是：

0：基环树上必不选的树边，1：树上的边，2：基环树环上方向 L 的边，3：基环树环上方向 R 的边 4：基环树上必选的树边

0：直接跳过。

1：分类讨论，是 $x$一侧的点为外向树树根时这条边会做贡献，还是 $y$一侧，化为 dfs 序区间在线段树上修改，查询最大值。

2，3：直接开个数组记录一下

4：直接加上贡献

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=500005;
int n,m,T,Q,tot,tim,top,ccnt,tcnt,ans;
int a[N],b[N],h[N],ne[N<<1],to[N<<1],w[N<<1],rev[N<<1];
int vis[N],dsu[N],tag[N],typ[N<<1];
int in[N],out[N],fa[N],tr[N<<2],lz[N<<2],rt[N];
int st[N],id[N<<1],Lv[N],Rv[N];
//typ: 边的类型，Lv: 基环树方向 L 的边权和，Rv: 基环树方向 R 的边权和
//dsu: 并查集，rev: 反向边，id: 基环树边记录基环树编号，树边记录根

void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int getdsu(int x) {return x==dsu[x]?x:dsu[x]=getdsu(dsu[x]);}

void pd(int i) {
    int l=i<<1,r=(i<<1)|1;
    tr[l]+=lz[i],tr[r]+=lz[i],lz[l]+=lz[i],lz[r]+=lz[i],lz[i]=0;
}
void modify(int l,int r,int s,int t,int i,int v) {
    if(l<=s&&t<=r) {lz[i]+=v,tr[i]+=v;return;}
    int mid=(s+t)>>1;if(lz[i]) pd(i);
    if(l<=mid) modify(l,r,s,mid,i<<1,v);
    if(mid+1<=r) modify(l,r,mid+1,t,(i<<1)|1,v);
    tr[i]=max(tr[i<<1],tr[(i<<1)|1]);
}
int query(int l,int r,int s,int t,int i) {
    if(l<=s&&t<=r) return tr[i];
    int mid=(s+t)>>1,re=0; if(lz[i]) pd(i);
    if(l<=mid) re=query(l,r,s,mid,i<<1);
    if(mid+1<=r) re=max(re,query(l,r,mid+1,t,(i<<1)|1));
    return re;
}
void work_tree(int t,int v) {//分类讨论某条树边对整棵树不同根时的影响
    int x=to[t],y=to[rev[t]];
    if(x==fa[y]) modify(in[y],out[y],1,tim,1,v);
    else modify(in[id[t]],out[id[t]],1,tim,1,v),modify(in[x],out[x],1,tim,1,-v);
}

void dfs_tree(int x,int rt,int las) {
    in[x]=++tim,fa[x]=las,vis[x]=1;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las)
            dfs_tree(to[i],rt,x),id[i]=id[rev[i]]=rt,typ[i]=typ[rev[i]]=1;
    out[x]=tim;
}
void dfs_circle(int x,int y,int no,int las) {
    fa[x]=las,vis[x]=1;
    if(x==y) {
        for(RI i=1;i<=top;++i) {
            typ[st[i]]=2,Lv[ccnt]+=w[st[i]];
            typ[rev[st[i]]]=3,Rv[ccnt]+=w[rev[st[i]]];
        }
    }
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&i!=no&&i!=rev[no]) {
            id[i]=id[rev[i]]=ccnt,typ[i]=4;
            st[++top]=i,dfs_circle(to[i],y,no,x),--top;
        }
}
void prework() {
    for(RI i=1;i<=m;++i) {
        if(vis[i]) continue;
        int k=getdsu(i);
        if(!tag[k]) dfs_tree(i,i,0),rt[++tcnt]=i;
        else {
            ++ccnt,dfs_circle(to[tag[k]],to[rev[tag[k]]],tag[k],0);
            id[tag[k]]=id[rev[tag[k]]]=ccnt;
            typ[tag[k]]=2,Lv[ccnt]+=w[tag[k]];
            if(tag[k]!=rev[tag[k]]) typ[rev[tag[k]]]=3,Rv[ccnt]+=w[rev[tag[k]]];//注意自环的特判
            ans+=max(Lv[ccnt],Rv[ccnt]);
        }
    }
    for(RI i=1;i<=tot;++i)
        if(typ[i]==4) ans+=w[i];
        else if(typ[i]==1) work_tree(i,w[i]);
    for(RI i=1;i<=tcnt;++i) ans+=query(in[rt[i]],out[rt[i]],1,tim,1);
}

void work() {
    Q=read(),printf("%d\n",ans);
    while(Q--) {
        int x=read()-ans*T,y=read()-ans*T;
        if(typ[x]==0);
        else if(typ[x]==1) {
            int kv=query(in[id[x]],out[id[x]],1,tim,1);
            work_tree(x,y-w[x]),w[x]=y;
            ans+=query(in[id[x]],out[id[x]],1,tim,1)-kv;
        }
        else if(typ[x]==2) {
            int kv=max(Lv[id[x]],Rv[id[x]]);
            Lv[id[x]]+=y-w[x],w[x]=y;
            ans+=max(Lv[id[x]],Rv[id[x]])-kv;
        }
        else if(typ[x]==3) {
            int kv=max(Lv[id[x]],Rv[id[x]]);
            Rv[id[x]]+=y-w[x],w[x]=y;
            ans+=max(Lv[id[x]],Rv[id[x]])-kv;
        }
        else if(typ[x]==4) ans+=y-w[x],w[x]=y;
        printf("%d\n",ans);
    }
}

int main()
{
    n=read(),m=read(),T=read();
    for(RI i=0;i<n;++i) a[i]=read();
    for(RI i=0;i<n;++i) b[i]=read();
    for(RI i=1;i<=m;++i) dsu[i]=i;
    for(RI i=0;i<n;++i) {
        int x=(a[i]+b[i])%m+1,y=(a[i]-b[i]+m)%m+1;
        if(x>y) swap(x,y);
        add(y,x,read());
        int r1=getdsu(x),r2=getdsu(y);
        if(r1==r2) tag[r1]=tot;
        else dsu[r1]=r2,tag[r2]|=tag[r1];
        if(x!=y) rev[tot]=tot+1,rev[tot+1]=tot,add(x,y,read());
        else rev[tot]=tot;
    }
    prework(),work();
    return 0;
}