2024-06-12 21:52:40
发布于：上海
58阅读
0回复
0点赞
为什么我的线段树AC洛谷原题P3368，ACGO全WA@_@
这两题没有一个字的区别吧。
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 500005
#define m(l,r) ((l+r)>>1)
#define ls(k) (k<<1)
#define rs(k) ((k<<1)|1)
struct node{
int l,r;
int dat,tag;
}t[4*MAXN+5];
int a[MAXN+1];
void build(int p, int l, int r){
t[p].l=l;
t[p].r=r;
t[p].tag=0;
if(l==r){t[p].dat=a[l]; return;}
int mid=m(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
inline void down(int p){
if(t[p].tag){
t[ls(p)].dat+=t[p].tag*(t[ls(p)].r-t[ls(p)].l+1);
t[rs(p)].dat+=t[p].tag*(t[rs(p)].r-t[rs(p)].l+1);
t[ls(p)].tag+=t[p].tag;
t[rs(p)].tag+=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int x,int y,int z){
if(x<=t[p].l && y>=t[p].r){
t[p].dat+=z*(t[p].r-t[p].l+1);
t[p].tag+=z;
return;
}
down(p);
int mid=m(t[p].l,t[p].r);
if(x<=mid) change(ls(p),x,y,z);
if(y>mid) change(rs(p),x,y,z);
t[p].dat=t[ls(p)].dat+t[rs(p)].dat;
}
int ask(int p,int x,int y){
if(x<=t[p].l && y>=t[p].r) return t[p].dat;
down(p);
int mid=m(t[p].l,t[p].r);
int ans=0;
if(x<=mid) ans+=ask(ls(p),x,y);
if(y>mid) ans+=ask(rs(p),x,y);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
int q,x,y,z;
cin>>q;
if(q==1){
cin>>x>>y>>z;
change(1,x,y,z);
}
else {
cin>>x;
cout<<ask(1,x,x)<<endl;
}
}
return 0;
}
盼大佬解答Orz stO
全部评论 9
经过我长达一个小时的研究，我终于找到这道题的问题在哪里了。数据出祸了（题目中要求x<=y，但是数据中会存在x>y的情况。所以用线段树会爆雷。新的数据我已经弄好了，等待上传。
2024-06-12 来自 浙江
3
有帮助，赞一个