Astk @ 2020-07-31 18:46:36
我偏不信，用数组写了一个线段树，查询的时候定义了一个新的变量存合并后的节点，然后进行查询。 我感觉这个想法没什么问题呀。 然而。。。。。。。它wa了. 下面是我的代码
#include<cstdio>
#include<iostream>
#define mid (l+r>>1)
#define N 500010
using namespace std;
int sum[N<<2],dat[N<<2],lmax[N<<2],rmax[N<<2],ans,n,m,a[N];
void up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
dat[rt]=max(dat[rt<<1],max(dat[rt<<1|1],rmax[rt<<1]+lmax[rt<<1|1]));
lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
rmax[rt]=max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
}
void build(int rt,int l,int r){
if(l==r){
sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=a[l];
return;
}
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
up(rt);
printf("rt:%d %d %d %d %d\n",rt,dat[rt],lmax[rt],rmax[rt],sum[rt]);
}
void change(int rt,int l,int r,int k,int val){
if(l==r){
sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=val;
return;
}
if(k<=mid) change(rt<<1,l,mid,k,val);
else change(rt<<1|1,mid+1,r,k,val);
up(rt);
}
int query(int rt,int l,int r,int L,int R){
if(L<=l&&R>=r){
return rt;
}
if(R<=mid) return query(rt<<1,l,mid,L,R);
if(L>mid)return query(rt<<1|1,mid+1,r,L,R);
int t1=query(rt<<1,l,mid,L,R),t2=query(rt<<1|1,mid+1,r,L,R);
printf("t1:%d t2:%d",t1,t2);
dat[ans]=max(dat[t1],max(dat[t2],rmax[t1]+lmax[t2]));
lmax[ans]=max(lmax[t1],sum[t1]+lmax[t2]);
rmax[ans]=max(rmax[t2],sum[t2]+rmax[t1]);
sum[ans]=sum[t1]+sum[t2];
printf("rt:%d %d %d %d %d\n",rt,dat[ans],lmax[ans],rmax[ans],sum[ans]);
return ans;
}
int main(){
ans=N<<2-1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==1){
if(x>y)swap(x,y);
printf("%d\n",dat[query(1,1,n,x,y)]);
}
else
change(1,1,n,x,y);
}
}用数组不能做是吗？
by 天命之路 @ 2020-07-31 19:55:19
@Astk 认同。
如果你觉得用不惯还可以用define
struct point{
int sum,lmax,rmax,dat,l,r;
#define sum(x) tr[x].sum
#define lmax(x) tr[x].lmax
#define rmax(x) tr[x].rmax
#define dat(x) tr[x].dat
#define l(x) tr[x].l
#define r(x) tr[x].r
}tr[N<<2];by Astk @ 2020-07-31 19:56:46
@天命之路 你这么一说，我灵光一现，我把数组开N*30； 多加一个计数器tot，用这个思想过了 https://www.luogu.com.cn/record/36140452
#include<cstdio>
#include<iostream>
#define mid (l+r>>1)
#define N 500010
using namespace std;
int sum[N<<5+2],dat[N<<5+2],lmax[N<<5+2],rmax[N<<5+2],ans,n,m,a[N+2],tot;
void up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
dat[rt]=max(dat[rt<<1],max(dat[rt<<1|1],rmax[rt<<1]+lmax[rt<<1|1]));
lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
rmax[rt]=max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
}
void build(int rt,int l,int r){
if(l==r){
sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=a[l];
return;
}
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
up(rt);
// printf("rt:%d %d %d %d %d\n",rt,dat[rt],lmax[rt],rmax[rt],sum[rt]);
}
void change(int rt,int l,int r,int k,int val){
if(l==r){
sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=val;
return;
}
if(k<=mid) change(rt<<1,l,mid,k,val);
else change(rt<<1|1,mid+1,r,k,val);
up(rt);
}
int query(int rt,int l,int r,int L,int R){
if(L<=l&&R>=r){
return rt;
}
if(R<=mid) return query(rt<<1,l,mid,L,R);
if(L>mid)return query(rt<<1|1,mid+1,r,L,R);
int t1=query(rt<<1,l,mid,L,R),t2=query(rt<<1|1,mid+1,r,L,R);
// printf("t1:%d t2:%d",t1,t2);
ans=++tot;
dat[ans]=max(dat[t1],max(dat[t2],rmax[t1]+lmax[t2]));
lmax[ans]=max(lmax[t1],sum[t1]+lmax[t2]);
rmax[ans]=max(rmax[t2],sum[t2]+rmax[t1]);
sum[ans]=sum[t1]+sum[t2];
// printf("rt:%d %d %d %d %d\n",rt,dat[ans],lmax[ans],rmax[ans],sum[ans]);
return ans;
}
int main(){
tot=(N<<2)+1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==1){
if(x>y)swap(x,y);
printf("%d\n",dat[query(1,1,n,x,y)]);
}
else
change(1,1,n,x,y);
}
}by Astk @ 2020-07-31 19:58:07
@天命之路 嗯嗯，我看见过你这种写法，一直没改，以后再尝试一下吧。
by Astk @ 2020-07-31 19:59:25
过了过了，它N*30空间也能过，@万弘
by 天命之路 @ 2020-07-31 19:59:41
@Astk 其实，加法运算的优先级高于位运算，所以：
N<<5+2=N<<7=128*N
by Astk @ 2020-07-31 20:00:20
没毛病 @天命之路
by 天命之路 @ 2020-07-31 20:01:06
其实你开的是
by Astk @ 2020-07-31 20:01:36
@天命之路 嗯，对，我说你说的没毛病
by Astk @ 2020-07-31 20:01:50
@天命之路 可以，细节