#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;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 45.16 us | 64 KB | Wrong Answer | Score: 0 | 显示更多 |