代码

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
	int x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN = 100005;
long long fa[MAXN],r[MAXN],st[MAXN],ch[MAXN][2];
long long a[MAXN],s[MAXN],tag[MAXN],size[MAXN];
int n,q;

inline bool notroot(int x)
	{return ch[fa[x]][0]==x || ch[fa[x]][1]==x;}

inline void pushup(int x)
{
	s[x]=s[ch[x][0]]+s[ch[x][1]]+a[x];
	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}

inline void pushr(int x)
	{swap(ch[x][0],ch[x][1]),r[x]^=1;}

inline void pusha(int x,int k)
 	{a[x]+=k,s[x]+=size[x]*k,tag[x]+=k;}

inline void pushdown(int x)
{
    if(tag[x])
    {
        if(ch[x][0]) pusha(ch[x][0],tag[x]);
        if(ch[x][1]) pusha(ch[x][1],tag[x]);
        tag[x]=0;
    }
    if(!r[x]) return;
    if(ch[x][0]) pushr(ch[x][0]);
    if(ch[x][1]) pushr(ch[x][1]);
    r[x]=0;
}

inline void rotate(int x)
{
    int y=fa[x],z=fa[y];
    int k=ch[y][1]==x,w=ch[x][k^1];
    if(notroot(y)) ch[z][ch[z][1]==y]=x;
    ch[x][k^1]=y; ch[y][k]=w;
    if(w) fa[w]=y;
    fa[y]=x,fa[x]=z;
    pushup(y);
}

inline void splay(int x)
{
    int y=x,z=0; st[++z]=y;
    while(notroot(y)) st[++z]=y=fa[y];
    while(z) pushdown(st[z--]);
    while(notroot(x)) rotate(x);
    pushup(x);
}

inline void access(int x)
{
    for(int y=0;x;x=fa[x])
        splay(x),ch[x][1]=y,pushup(x),y=x;
}

inline void makeroot(int x)
	{access(x),splay(x),pushr(x);}

inline void split(int x,int y)
	{makeroot(x),access(y),splay(y);}

inline void link(int x,int y)
	{makeroot(x),fa[x]=y;}

inline long long query(int x,int y)
	{split(x,y); return s[y];}

inline void add(int x,int y,int k)
	{split(x,y),pusha(y,k);}

int main(int argc, char const *argv[])
{
    n=2; q=1;
    for(int i = 1; i < n; ++i) 
    	link(i,i+1);
    for(int i = 1; i <= n; ++i)
    	a[i]=read(),size[i]=1;
    int opt,x,y,k;
    while(q--)
    {
    	opt=2; x=1; y=2;
        if(opt==1) add(x,y,read());
        if(opt==2) printf("%lld\n", query(x,y));
    }
	return 0;
}

评测结果