残废代码库（自用

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
int q[200007];
int n,m,r,mod;
//Segment tree
struct ahh{
    int l,r,tag;
    long long v;
}a[1600007];
void build(int ll,int rr,int i)
{
    a[i].l=ll;
    a[i].r=rr;
    if(ll==rr){a[i].v=q[ll]%mod;return;}
    int mid=(ll+rr)>>1;
    build(ll,mid,(i<<1));
    build(mid+1,rr,((i<<1)|1));
    a[i].v=(a[(i<<1)].v+a[((i<<1)|1)].v)%mod;
    return;
}
int ad;
void add(int ll,int rr,int i)
{
    if(ll==a[i].l&&rr==a[i].r){a[i].tag+=ad;return;}
    a[i].v=(a[i].v+(rr-ll+1)*ad)%mod;
    int mid=(a[i].l+a[i].r)>>1;
    if(rr<=mid)add(ll,rr,(i<<1));
    else if(ll>=mid+1)add(ll,rr,((i<<1)|1));
    else{add(ll,mid,(i<<1));add(mid+1,rr,((i<<1)|1));}
    return;
}
void pushtag(int i)
{
    if(!a[i].tag)return;
    a[i].v=(a[i].v+(a[i].r-a[i].l+1)*ad)%mod;
    if(a[i].l==a[i].r){a[i].tag=0;return;}
    a[(i<<1)].tag+=a[i].tag;
    a[((i<<1)|1)].tag+=a[i].tag;
    a[i].tag=0;
    return;
}
int find(int ll,int rr,int i)
{
    pushtag(i);
    if(a[i].l==ll&&a[i].r==rr)return a[i].v;
    int mid=(a[i].l+a[i].r)>>1;
    if(rr<=mid)return (find(ll,rr,(i<<1)))%mod;
    else if(ll>=mid+1)return (find(ll,rr,((i<<1)|1)))%mod;
    else return (find(ll,mid,(i<<1))+find(mid+1,rr,((i<<1)|1)))%mod;
}
//build tree
int s[100007];
struct emm{
    int e,f;
}b[200007];
int h[100007];
int cc=0;
void con(int x,int y)
{
    b[++cc].f=h[x];
    h[x]=cc;
    b[cc].e=y;
    return;
}
int fa[100007];
int siz[100007];
int mac[100007];
int z[100007];
int d[100007];
void dfs(int x)
{
    //int flag=0;
    siz[x]=1;
    for(int i=h[x];i;i=b[i].f)
    if(!d[b[i].e])
    {
      //  flag++;
        fa[b[i].e]=x;
        d[b[i].e]=d[x]+1;
        dfs(b[i].e);
        siz[x]+=siz[b[i].e];
        if(siz[b[i].e]>mac[x])
        {
            mac[x]=siz[b[i].e];
            z[x]=b[i].e;
        }
    }
    return;
}
int tot=0;
int in[100007];
int out[100007];
int top[100007];
void dfss(int x,int tp)
{
    q[++tot]=s[x];
    in[x]=tot;
    top[x]=tp;
    //if(!z[x]){q[++tot]=x;out[x]=tot;return;}
    if(z[x])dfss(z[x],tp);
    for(int i=h[x];i;i=b[i].f)
    if(b[i].e!=fa[x]&&b[i].e!=z[x])
    dfss(b[i].e,b[i].e);
    q[++tot]=s[x];
    out[x]=tot;
    return;
}
//Qtree
//int top[100007];
int fitop(int x)
{
    if(z[fa[x]]==x)return top[x]=fitop(fa[x]);
    return top[x]=x;
}
void change(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]>d[top[y]])swap(x,y);
        add(in[top[y]],in[y],1);y=fa[top[y]];
    }
    if(d[x]>d[y])swap(x,y);
    add(in[y],in[x],1);
    return;
}
int fin(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(d[top[x]]>d[top[y]])swap(x,y);
        ans+=find(in[top[y]],in[y],1);
        ans%=mod;
        y=fa[top[y]];
    }
    if(d[x]>d[y])swap(x,y);
    ans+=find(in[y],in[x],1);
    return ans%mod;
}
//main
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&r,&mod);
    for(R int i=1;i<=n;++i)
    {
        scanf("%d",&s[i]);
        s[i]%=mod;
    }
    for(R int i=1;i<=n-1;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        con(x,y);
        con(y,x);
    }
    fa[r]=1,d[r]=1;
    dfs(r);
    fa[r]=0;
    dfss(r,r);
    build(1,tot,1);
    for(R int i=1;i<=n;++i)
    if(!top[i])fitop(i);
    for(R int i=1;i<=m;++i)
    {
        int ch;
        scanf("%d",&ch);
        //cout<<i<<endl;
        if(ch==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            ad=z;
            change(x,y);
        }
        if(ch==2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d
",(fin(x,y))%mod);
        }
        if(ch==3)
        {
            int x,z;
            scanf("%d%d",&x,&z);
            ad=z;
            //cout<<in[x]<<" "<<out[x]<<endl;
            add(in[x],out[x]-1,1);
        }
        if(ch==4)
        {
            int x;
            scanf("%d",&x);
            printf("%d
",find(in[x],out[x]-1,1)%mod);
        }
    }
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=3e5;
long long tu[2][MAXN];
long long hs[2][MAXN];
long long ps[2][MAXN];
long long zz[2][MAXN];
long long hz[2][MAXN];
long long max(long long qaq,long long qwq){return qaq>qwq?qaq:qwq;}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
    scanf("%d",&tu[0][i]);
    hs[0][i]=hs[0][i-1]+tu[0][i];
    }
    for(int i=1;i<=n;++i)
    {
    scanf("%d",&tu[1][i]);
    hs[1][i]=hs[1][i-1]+tu[1][i];
    }
    int t=-1;
    for(int i=1;i<=n;i+=2)
    {
        ps[0][i]=ps[0][i-1]+(tu[0][i]*(++t));
        ps[1][i]=ps[0][i]+(tu[1][i]*(++t));
        ps[1][i+1]=ps[1][i]+(tu[1][i+1]*(++t));
        ps[0][i+1]=ps[1][i+1]+(tu[0][i+1]*(++t));
        //cout<<ps[0][i]<<" "<<ps[1][i]<<" "<<ps[1][i+1]<<" "<<ps[0][i+1]<<endl;
    }
    for(int i=n;i;--i)
    {
        zz[0][i]=zz[0][i+1]+hs[0][n]-hs[0][i-1];
        zz[1][i]=zz[1][i+1]+hs[1][n]-hs[1][i-1];
        //cout<<zz[0][i]<<" "<<zz[1][i]<<endl;
    }
    for(int i=1;i<=n;++i)
    {
        hz[0][i]=(hs[0][n]-hs[0][i-1])*(n-i+1)-zz[0][i];
        hz[1][i]=(hs[1][n]-hs[1][i-1])*(n-i+1)-zz[1][i];
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        ans=max(ans,ps[0][i-1]+(i*2-1-1)*(hs[0][n]-hs[0][i-1])+zz[0][i+1]+(i+n-1)*(hs[1][n]-hs[1][i-1])+hz[1][i]);
        cout<<ans<<endl;
        ans=max(ans,ps[1][i-1]+(i*2-1)*(hs[1][n]-hs[1][i-1])+zz[1][i+1]+(i+n-1)*(hs[0][n]-hs[0][i-1])+hz[0][i+1]);
        cout<<ans<<endl;
    }
    cout<<ans;
    return 0;
}