怒りの水GSS
15038 ワード
先日QTREE 4に虐げられたのは軽くなくて、今日zyhはまたQTREE 4が動的な点で分治することができると言って、毛の私の動的な点の分治のためにいつも4番目の点WAで、科学は何がありますか.
そこで義憤に満ちて、私はGSSをして、またTATに虐げられました.
GSS1:
GSS2:
GSS3:
GSS4:
GSS5:
GSS6:
GSS7:
もう吐きました.もう線分の木は見たくありません(手動でさようなら)
そこで義憤に満ちて、私はGSSをして、またTATに虐げられました.
GSS1:
<span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<cstring>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=50000+5;
struct Node{
int l,r,lm,rm,mx,sum;
}tr[N<<2];
int a[N];
void pushup(int o){
tr[o].mx=max(tr[lc].rm+tr[rc].lm,max(tr[lc].mx,tr[rc].mx));
tr[o].sum=tr[lc].sum+tr[rc].sum;
tr[o].lm=max(tr[lc].lm,tr[lc].sum+tr[rc].lm);
tr[o].rm=max(tr[rc].rm,tr[lc].rm+tr[rc].sum);
}
void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;
if(l==r)tr[o].lm=tr[o].rm=tr[o].mx=tr[o].sum=a[l];
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
pushup(o);
}
}
Node query(int o,int a,int b){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o];
else{
int m=l+r>>1;
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else{
Node lans=query(lc,a,m),rans=query(rc,m+1,b),ans;
ans.sum=lans.sum+rans.sum;
ans.mx=max(lans.rm+rans.lm,max(lans.mx,rans.mx));
ans.lm=max(lans.lm,lans.sum+rans.lm);
ans.rm=max(rans.rm,lans.rm+rans.sum);
return ans;
}
}
}
int main(){
int n,m;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
int a,b;
while(m--){
scanf("%d%d",&a,&b);
printf("%d
",query(1,a,b).mx);
}
return 0;
}</span>
GSS2:
<span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=100000+5;
typedef long long ll;
struct Node{
int l,r;
ll val,add,maxval,maxadd;
}tr[N<<2];
struct Query{
int l,r,id;
bool operator<(const Query &rhs)const{
return r<rhs.r;
}
}q[N];
void pushup(int o){
tr[o].val=max(tr[lc].val,tr[rc].val);
tr[o].maxval=max(tr[lc].maxval,tr[rc].maxval);
}
void pushdown(int o){
if(tr[o].add){
tr[lc].maxadd=max(tr[lc].maxadd,tr[o].maxadd+tr[lc].add);
tr[rc].maxadd=max(tr[rc].maxadd,tr[o].maxadd+tr[rc].add);
tr[lc].add+=tr[o].add;tr[rc].add+=tr[o].add;
tr[lc].maxval=max(tr[lc].maxval,tr[lc].val+tr[o].maxadd);
tr[rc].maxval=max(tr[rc].maxval,tr[rc].val+tr[o].maxadd);
tr[lc].val+=tr[o].add;tr[rc].val+=tr[o].add;
tr[o].add=0;tr[o].maxadd=0;
}
}
void update(int o,int a,int b,ll x){
int l=tr[o].l,r=tr[o].r;
if(a==l&&b==r){
tr[o].add+=x;
tr[o].maxadd=max(tr[o].maxadd,tr[o].add);
tr[o].val+=x;
tr[o].maxval=max(tr[o].maxval,tr[o].val);
//printf("%d %d %lld %lld %lld %lld
",l,r,tr[o].val,tr[o].add,tr[o].maxval,tr[o].maxadd);
}else{
int m=l+r>>1;
pushdown(o);
if(b<=m)update(lc,a,b,x);
else if(m<a)update(rc,a,b,x);
else update(lc,a,m,x),update(rc,m+1,b,x);
pushup(o);
}
}
ll query(int o,int a,int b){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o].maxval;
else{
int m=l+r>>1;
pushdown(o);
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else return max(query(lc,a,m),query(rc,m+1,b));
}
}
void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;
if(l==r)return;
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
pushup(o);
}
}
ll ans[N],a[N];
map<int,int>mp;
int main(){
int n;scanf("%d",&n);build(1,1,n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
mp[a[i]]=0;
}
int m;scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;
}
sort(q+1,q+1+m);
int j=1;
for(int i=1;i<=n;i++){
//printf("%d
",i);
update(1,mp[a[i]]+1,i,a[i]);
mp[a[i]]=i;
while(q[j].r==i){
ans[q[j].id]=query(1,q[j].l,q[j].r);
j++;
}
}
for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
return 0;
}</span>
GSS3:
#include<iostream>
#include<cstdio>
#include<cstring>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=50000+5;
typedef long long ll;
struct Node{
int l,r;
ll sum,mx,lm,rm;
}tr[N<<2];
int a[N];
Node merge(Node l,Node r){
Node ans;
ans.l=l.l;ans.r=r.r;
ans.sum=l.sum+r.sum;
ans.mx=max(l.rm+r.lm,max(l.mx,r.mx));
ans.lm=max(l.lm,l.sum+r.lm);
ans.rm=max(r.rm,l.rm+r.sum);
return ans;
}
void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;
if(l==r)tr[o].sum=tr[o].mx=tr[o].lm=tr[o].rm=a[l];
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
tr[o]=merge(tr[lc],tr[rc]);
}
}
Node query(int o,int a,int b){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o];
else{
int m=l+r>>1;
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else return merge(query(lc,a,m),query(rc,m+1,b));
}
}
void update(int o,int p,int v){
int l=tr[o].l,r=tr[o].r;
if(l==r)tr[o].sum=tr[o].mx=tr[o].lm=tr[o].rm=v;
else{
int m=l+r>>1;
if(p<=m)update(lc,p,v);
else update(rc,p,v);
tr[o]=merge(tr[lc],tr[rc]);
}
}
int main(){
int n,m;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
int opt,x,y;
while(m--){
scanf("%d%d%d",&opt,&x,&y);
if(opt)printf("%lld
",query(1,x,y).mx);
else update(1,x,y);
}
return 0;
}
GSS4:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=100000+5;
typedef long long ll;
struct Node{
int l,r;
ll sum;
bool mark;
}tr[N<<2];
void pushup(int o){
tr[o].sum=tr[lc].sum+tr[rc].sum;
tr[o].mark=tr[lc].mark||tr[rc].mark;
}
void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;
tr[o].mark=true;
if(l==r)scanf("%lld",&tr[o].sum);
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
pushup(o);
}
}
void update(int o,int a,int b){
if(!tr[o].mark)return;
int l=tr[o].l,r=tr[o].r;
if(l==r){
tr[o].sum=(ll)sqrt(tr[o].sum);
if(tr[o].sum<=1)tr[o].mark=false;
}else{
int m=l+r>>1;
if(b<=m)update(lc,a,b);
else if(m<a)update(rc,a,b);
else{
update(lc,a,m);update(rc,m+1,b);
}
pushup(o);
}
}
ll query(int o,int a,int b){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o].sum;
else{
int m=l+r>>1;
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else return query(lc,a,m)+query(rc,m+1,b);
}
}
int main(){
int kase=0;
int n;
while(scanf("%d",&n)==1){
printf("Case #%d:
",++kase);
build(1,1,n);
int m;scanf("%d",&m);
int opt;int x,y;
while(m--){
scanf("%d%d%d",&opt,&x,&y);
if(x>y)swap(x,y);
if(opt)
printf("%lld
",query(1,x,y));
else update(1,x,y);
}
printf("
");
}
return 0;
}
GSS5:
#include<iostream>
#include<cstdio>
#include<cstring>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=10000+5;
struct Node{
int l,r,lm,rm,sum,mx;
}tr[N<<2];
int a[N],pr[N];
Node merge(Node lans,Node rans){
Node ans;
ans.lm=max(lans.lm,lans.sum+rans.lm);
ans.rm=max(rans.rm,rans.sum+lans.rm);
ans.sum=lans.sum+rans.sum;
ans.mx=max(lans.rm+rans.lm,max(lans.mx,rans.mx));
return ans;
}
void build(int o,int l,int r){
if(l==r)
tr[o].rm=tr[o].sum=tr[o].mx=tr[o].lm=a[l];
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
tr[o]=merge(tr[lc],tr[rc]);
}
tr[o].l=l;tr[o].r=r;
}
Node query(int o,int a,int b){
if(a>b)return (Node){0};
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o];
else{
int m=l+r>>1;
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else return merge(query(lc,a,m),query(rc,m+1,b));
}
}
int sum(int i,int j){
return pr[j]-pr[i-1];
}
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),pr[i]=pr[i-1]+a[i];
build(1,1,n);
int m;scanf("%d",&m);
int x1,y1,x2,y2;
while(m--){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(y1<x2)printf("%d
",query(1,x1,y1).rm+sum(y1+1,x2-1)+query(1,x2,y2).lm);
else printf("%d
",max(query(1,x2,y1).mx,max(query(1,x1,x2).rm+query(1,x2,y2).lm-a[x2],query(1,x1,y1).rm+query(1,y1,y2).lm-a[y1])));
}
}
return 0;
}
GSS6:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200000+5;
const int inf=1e9;
int fa[N],ch[N][2],root;
int id[N],cnt;
int v[N],sum[N],sz[N],mx[N],lm[N],rm[N];
int a[N];
void pushup(int x){
int l=ch[x][0],r=ch[x][1];
sz[x]=sz[l]+sz[r]+1;
sum[x]=sum[l]+sum[r]+v[x];
mx[x]=max(rm[l]+v[x]+lm[r],max(mx[l],mx[r]));
lm[x]=max(lm[l],sum[l]+lm[r]+v[x]);
rm[x]=max(rm[r],sum[r]+rm[l]+v[x]);
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l=ch[y][1]==x,r=l^1;
if(y==k)k=x;
else ch[z][ch[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
int y,z;
while(x!=k){
y=fa[x],z=fa[y];
if(y!=k){
if(ch[y][0]==x^ch[z][0]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int kth(int x,int k){
int r=sz[ch[x][0]]+1;
if(r==k)return x;
else if(k<r)return kth(ch[x][0],k);
else return kth(ch[x][1],k-r);
}
int split(int a,int b){
int x=kth(root,a),y=kth(root,b+2);
splay(x,root);splay(y,ch[x][1]);
return ch[y][0];
}
void insert(int k,int val){
int x=kth(root,k),y=kth(root,k+1);
splay(x,root);splay(y,ch[x][1]);
x=y;
ch[x][0]=++cnt;
sum[cnt]=mx[cnt]=v[cnt]=val;
if(val>=0)rm[cnt]=lm[cnt]=val;
else rm[cnt]=lm[cnt]=0;
fa[cnt]=x;sz[cnt]=1;
pushup(x);pushup(fa[x]);
}
void del(int k){
int x=split(k,k),y=fa[x];
ch[y][0]=fa[x]=0;
pushup(y);pushup(fa[y]);
}
void change(int k,int val){
int x=split(k,k),y=fa[x];
sum[x]=v[x]=mx[x]=val;
if(val>=0)rm[x]=lm[x]=val;
else rm[x]=lm[x]=0;
pushup(y);pushup(fa[y]);
}
void build(int l,int r,int f){
if(l>r)return;
int mid=l+r>>1,now=id[mid],last=id[f];
if(l==r){
sum[now]=mx[now]=a[l];sz[now]=1;
if(a[l]>=0)lm[now]=rm[now]=a[l];
else lm[now]=rm[now]=0;
}else build(l,mid-1,mid),build(mid+1,r,mid);
v[now]=a[mid];fa[now]=last;pushup(now);
ch[last][mid>=f]=now;
}
int main(){
int n;scanf("%d",&n);
mx[0]=a[1]=a[n+2]=-inf;
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
for(int i=1;i<=n+2;i++)id[i]=i;
build(1,n+2,0);root=(n+3)>>1;cnt=n+2;
int m;scanf("%d",&m);
char opt[10];
int x,y;
while(m--){
scanf("%s",opt);
if(opt[0]=='D'){
scanf("%d",&x);
del(x);
}else{
scanf("%d%d",&x,&y);
if(opt[0]=='I')insert(x,y);
else if(opt[0]=='R')change(x,y);
else{
int ans=split(x,y);
printf("%d
",mx[ans]);
}
}
}
return 0;
}
GSS7:
#include<iostream>
#include<cstdio>
#include<cstring>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int N=100000+5;
struct Node{
int l,r,mx,lm,rm,sum,set;
bool mark;
}tr[N<<2];
int a[N];
void merge(Node lans,Node rans,Node &ans){
ans.mx=max(lans.rm+rans.lm,max(lans.mx,rans.mx));
ans.lm=max(lans.lm,lans.sum+rans.lm);
ans.rm=max(rans.rm,rans.sum+lans.rm);
ans.sum=lans.sum+rans.sum;
}
void pushdown(int o){
if(tr[o].mark){
tr[lc].mark=tr[rc].mark=true;tr[o].mark=false;
int len=tr[o].r-tr[o].l+1;
tr[lc].lm=tr[lc].rm=tr[lc].sum=tr[lc].mx=tr[o].set*(len-(len>>1));
tr[rc].mx=tr[rc].lm=tr[rc].rm=tr[rc].sum=tr[o].set*(len>>1);
tr[lc].set=tr[rc].set=tr[o].set;
}
}
void update(int o,int a,int b,int v){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r){
tr[o].mx=tr[o].lm=tr[o].rm=tr[o].sum=v*(r-l+1);
tr[o].set=v;
tr[o].mark=true;
}else{
int m=l+r>>1;
pushdown(o);
if(b<=m)update(lc,a,b,v);
else if(m<a)update(rc,a,b,v);
else update(lc,a,m,v),update(rc,m+1,b,v);
merge(tr[lc],tr[rc],tr[o]);
}
}
void build(int o,int l,int r){
tr[o].l=l;tr[o].r=r;tr[o].mark=false;
if(l==r)tr[o].mx=tr[o].lm=tr[o].rm=tr[o].sum=a[l];
else{
int m=l+r>>1;
build(lc,l,m);build(rc,m+1,r);
merge(tr[lc],tr[rc],tr[o]);
}
}
Node query(int o,int a,int b){
int l=tr[o].l,r=tr[o].r;
if(l==a&&b==r)return tr[o];
else{
pushdown(o);
Node ans;
int m=l+r>>1;
if(b<=m)return query(lc,a,b);
else if(m<a)return query(rc,a,b);
else{
merge(query(lc,a,m),query(rc,m+1,b),ans);
return ans;
}
}
}
struct Edge{int to,next;}e[N<<1];
int head[N],cnt;
void ins(int u,int v){
e[++cnt]=(Edge){v,head[u]};head[u]=cnt;
}
int fa[N],dep[N],siz[N],son[N],top[N],pos[N],rank[N],sz;
void dfs(int u){
siz[u]=1;son[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;if(v==fa[u])continue;
dep[v]=dep[u]+1;fa[v]=u;
dfs(v);
siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs(int u,int tp){
top[rank[pos[u]=++sz]=u]=tp;
if(son[u])dfs(son[u],tp);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v!=son[u]&&v!=fa[u])dfs(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
return dep[u]<dep[v]?u:v;
}
int query(int u,int v){
if(pos[u]>pos[v])swap(u,v);
Node lans={0},rans={0};
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
merge(query(1,pos[top[u]],pos[u]),lans,lans);
u=fa[top[u]];
}else{
merge(query(1,pos[top[v]],pos[v]),rans,rans);
v=fa[top[v]];
}
}
if(dep[u]<dep[v]){
merge(query(1,pos[u],pos[v]),rans,rans);
return max(max(0,rans.lm+lans.lm),max(rans.mx,lans.mx));
}else{
merge(query(1,pos[v],pos[u]),lans,lans);
}
return max(max(0,rans.lm+lans.lm),max(rans.mx,lans.mx));
}
void update(int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,pos[top[u]],pos[u],w);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
update(1,pos[u],pos[v],w);
}
int val[N];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
ins(u,v);ins(v,u);
}
dfs(1);dfs(1,1);
for(int i=1;i<=n;i++)a[pos[i]]=val[i];
build(1,1,n);
int m;scanf("%d",&m);
int w,opt;
while(m--){
scanf("%d%d%d",&opt,&u,&v);
if(opt==1)printf("%d
",query(u,v));
else {
scanf("%d",&w);
update(u,v,w);
}
}
return 0;
}
もう吐きました.もう線分の木は見たくありません(手動でさようなら)