kobebraint @ 2024-08-02 12:07:15
cerr是调试用的,不影响正常输出
机房里好多佬也没看出来哪里有问题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
#define forn(i,n) for(ll i=1;i<=n;i++)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define fin(a) freopen(a,"r",stdin)
#define fout(a) freopen(a,"w",stdout)
#define ferr(a) freopen(a,"w",stderr)
ll n,m,a[1000500],segment_tree[4000500],
op,x,y,k,lazy_tag[4000500];
void build_segment_tree(ll l,ll r,ll k){
if(l==r){
segment_tree[k]=a[l];
return;
}
ll mid=(l+r)>>1;
build_segment_tree(l,mid,k<<1);
build_segment_tree(mid+1,r,k<<1|1);
segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}
void push_down(ll l,ll r,ll mid,ll k){
segment_tree[k<<1]+=(mid-l+1)*lazy_tag[k];
segment_tree[k<<1|1]+=(r-mid)*lazy_tag[k];
lazy_tag[k<<1]+=lazy_tag[k];
lazy_tag[k<<1|1]+=lazy_tag[k];
lazy_tag[k]=0;
}
//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll s,ll e,ll x){
cerr<<1<<"#\n";
if(s<=l&&r<=e){
segment_tree[k]+=(e-s+1)*x;
lazy_tag[k]+=x;
return;
}
ll mid=(l+r)>>1;
if(lazy_tag[k]&&l!=r){
push_down(l,r,mid,k);
}
if(l<=mid){
addition_segment_tree(l,mid,k<<1,s,e,x);
}
if(r>mid){
addition_segment_tree(mid+1,r,k<<1|1,s,e,x);
}
}
//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k,ll s,ll e){
cerr<<2<<"#\n";
if(s<=l&&e>=r){
return segment_tree[k];
}
ll mid=(l+r)>>1,sum;
if(lazy_tag[k]){
push_down(l,r,mid,k);
}
cerr<<"**^\n";
sum=sum_segment_tree(l,mid,k<<1,s,e);
sum+=sum_segment_tree(mid+1,r,k<<1|1,s,e);
cerr<<3<<"#\n";
return sum;
}
int main(){
cin>>n>>m;
cerr<<m<<endl;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
build_segment_tree(1,n,1);
cerr<<"*"<<m<<endl;
for(long long i=1;i<=m;i++){
cin>>op>>x>>y;
cerr<<"##"<<op<<"#"<<i<<endl;
if(op==1){
cin>>k;
cerr<<"4#\n";
addition_segment_tree(1,n,1,x,y,k);
}else{
cerr<<"5#\n";
cout<<sum_segment_tree(1,n,1,x,y)<<endl;
}
}
return 0;
}
by zzbzwjx @ 2024-08-02 12:52:04
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define cl(a) memset(a,0,sizeof a)
//#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
//#define forn(i,n) for(ll i=1;i<=n;i++)
//#define copy(a,b) copy(begin(a),end(a),begin(b))
//#define fin(a) freopen(a,"r",stdin)
//#define fout(a) freopen(a,"w",stdout)
//#define ferr(a) freopen(a,"w",stderr)
ll n,m,a[100500],segment_tree[400500],op,x,y,k,lazy_tag[400500];
void build_segment_tree(ll l,ll r,ll k){
if(l==r){
segment_tree[k]=a[l];
return;
}
ll mid=(l+r)/2;
build_segment_tree(l,mid,k*2);
build_segment_tree(mid+1,r,k*2+1);
segment_tree[k]=segment_tree[k*2]+segment_tree[k*2+1];
}
void addition(int k,int l,int r,int tag_){
lazy_tag[k]+=tag_;
segment_tree[k]+=(r-l+1)*tag_;
}
void push_down(ll l,ll r,ll mid,ll k){
if(!segment_tree[k])return;
addition(k*2,l,mid,lazy_tag[k]);
addition(k*2+1,mid+1,r,lazy_tag[k]);
lazy_tag[k]=0;
}
//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll x){
// cerr<<1<<"#\n";
if(x<=l&&r<=y){
addition(k,l,r,x);
return;
}
ll mid=(l+r)/2;
// if(lazy_tag[k]&&l!=r)
push_down(l,r,mid,k);
if(x<=mid){
addition_segment_tree(l,mid,k*2,x);
}
if(y>mid){
addition_segment_tree(mid+1,r,k*2+1,x);
}
segment_tree[k]=segment_tree[k*2]+segment_tree[k*2+1];
}
//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k){
// cerr<<2<<"#\n";
if(x>r||y<l)return 0;
if(x<=l&&y>=r){
return segment_tree[k];
}
ll mid=(l+r)>>1,sum=0;
// if(lazy_tag[k])
push_down(l,r,mid,k);
// cerr<<"**^\n";
sum+=sum_segment_tree(l,mid,k*2);
sum+=sum_segment_tree(mid+1,r,k*2+1);
// cerr<<3<<"#\n";
return sum;
}
int main(){
cin>>n>>m;
cerr<<m<<endl;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
build_segment_tree(1,n,1);
// cerr<<"*"<<m<<endl;
for(long long i=1;i<=m;i++){
cin>>op>>x>>y;
// cerr<<"##"<<op<<"#"<<i<<endl;
if(op==1){
cin>>k;
// cerr<<"4#\n";
addition_segment_tree(1,n,1,k);
}else{
// cerr<<"5#\n";
cout<<sum_segment_tree(1,n,1)<<endl;
}
}
return 0;
}
不RE了成全WA了
by kobebraint @ 2024-08-02 13:38:28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
#define forn(i,n) for(ll i=1;i<=n;i++)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define fin(a) freopen(a,"r",stdin)
#define fout(a) freopen(a,"w",stdout)
#define ferr(a) freopen(a,"w",stderr)
ll n,m,a[1000500],segment_tree[4000500],
op,x,y,k,lazy_tag[4000500];
void build_segment_tree(ll l,ll r,ll k){
if(l==r){
segment_tree[k]=a[l];
return;
}
ll mid=(l+r)>>1;
build_segment_tree(l,mid,k<<1);
build_segment_tree(mid+1,r,k<<1|1);
segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}
void push_down(ll l,ll r,ll mid,ll k){
segment_tree[k<<1]+=(mid-l+1)*lazy_tag[k];
segment_tree[k<<1|1]+=(r-mid)*lazy_tag[k];
lazy_tag[k<<1]+=lazy_tag[k];
lazy_tag[k<<1|1]+=lazy_tag[k];
lazy_tag[k]=0;
}
//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll s,ll e,ll x){
if(s<=l&&r<=e){
segment_tree[k]+=(e-s+1)*x;
lazy_tag[k]+=x;
return;
}
ll mid=(l+r)>>1;
if(lazy_tag[k]&&l!=r){
push_down(l,r,mid,k);
}
if(s<=mid){
addition_segment_tree(l,mid,k<<1,s,e,x);
}
if(e>mid){
addition_segment_tree(mid+1,r,k<<1|1,s,e,x);
}
segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}
//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k,ll s,ll e){
if(s<=l&&e>=r){
return segment_tree[k];
}
if(s>r||e<l){
return 0;
}
ll mid=(l+r)>>1,sum;
if(lazy_tag[k]){
push_down(l,r,mid,k);
}
if(s<=mid){
sum=sum_segment_tree(l,mid,k<<1,s,e);
}
if(e>mid){
sum+=sum_segment_tree(mid+1,r,k<<1|1,s,e);
}
return sum;
}
int main(){
cin>>n>>m;
cerr<<m<<endl;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
build_segment_tree(1,n,1);
for(long long i=1;i<=m;i++){
cin>>op>>x>>y;
if(op==1){
cin>>k;
addition_segment_tree(1,n,1,x,y,k);
}else{
cout<<sum_segment_tree(1,n,1,x,y)<<endl;
}
}
return 0;
}
by kobebraint @ 2024-08-02 13:43:51
目前是有输出,但是wa
by lcy0506 @ 2024-08-02 13:57:31
#include <bits/stdc++.h>
using namespace std;
long long a[1000001],sum[4000001],add[4000001];
inline void build(long long l,long long r,long long k)
{
if(l==r)
{
sum[k]=a[l];
return;
}
long long mid=(l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline void Add(long long l,long long r,long long k,long long q)
{
add[k]+=q;
sum[k]+=q*(r-l+1);
}
inline void pushdown(long long l,long long r,long long k)
{
if(!add[k])
return;
long long mid=(l+r)>>1;
Add(l,mid,k<<1,add[k]);
Add(mid+1,r,k<<1|1,add[k]);
add[k]=0;
}
inline void change(long long l,long long r,long long L,long long R,long long k,long long q)
{
if(L<=l&&r<=R)
{
Add(l,r,k,q);
return;
}
pushdown(l,r,k);
long long mid=(l+r)>>1;
if(L<=mid)
change(l,mid,L,R,k<<1,q);
if(R>mid)
change(mid+1,r,L,R,k<<1|1,q);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline long long query(long long l,long long r,long long L,long long R,long long k)
{
if(L<=l&&r<=R)
{
return sum[k];
}
pushdown(l,r,k);
long long mid=(l+r)>>1,res=0;
if(L<=mid) res+=query(l,mid,L,R,k<<1);
if(R>mid) res+=query(mid+1,r,L,R,k<<1|1);
return res;
}
int main()
{
long long n,m;
cin>>n>>m;
for(long long i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
for(long long i=1;i<=m;i++)
{
long long p,x,y,z;
cin>>p;
if(p==1)
{
cin>>x>>y>>z;
change(1,n,x,y,1,z);
}
else
{
cin>>x>>y;
cout<<query(1,n,x,y,1)<<endl;
}
}
}//2147483647
by lcy0506 @ 2024-08-02 13:57:48
@kobebraint
by kobebraint @ 2024-08-02 14:07:50
thx