线段树挂了求教
  • 板块P2357 守墓人
  • 楼主fzj2007
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/8/29 18:50
  • 上次更新2023/11/5 14:00:35
查看原帖
线段树挂了求教
172370
fzj2007楼主2020/8/29 18:50

RT......线段树写挂了全WA,求教,快读建议跳过!

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
//#include<conio.h>
#include<string>
#include<map>
#include<cstdlib>
#include<queue>
#include<math.h>
#include<time.h>
#include<set>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
using namespace std; 
using std::cin;
using std::cout;
using std::endl;
namespace IN{
    const int MAX_INPUT = 1000000;
    #define getc() (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
    char buf[MAX_INPUT],*p1,*p2;
    template<typename T>inline bool read(T &x) {
        static std::streambuf *inbuf=cin.rdbuf();
        x=0;
        register int f=0,flag=false;
        register char ch=getc();
        while(!isdigit(ch)){
            if (ch=='-') f=1;
        	ch=getc();
        }
        if(isdigit(ch)) x=x*10+ch-'0',ch=getc(),flag=true;
        while(isdigit(ch)) {
            x=x*10+ch-48;
            ch=getc();
        }
        x=f?-x:x;
        return flag;
    }
    template<typename T,typename ...Args>inline bool read(T& a,Args& ...args) {
       return read(a)&&read(args...);
    }
    #undef getc
}

namespace OUT{
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
    	for(register int i=0;i<s.length();i++) putc(s[i]);
	}
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);put(ch,args...);
    }
}
using namespace IN;
using namespace OUT;
#define int long long
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mid (l+r>>1)
int n,m,opt,l,r,k,a[200005];
struct node{
	int val,lazy;
}t[800005];
inline void push_up(int x){
	t[x].val=t[lc(x)].val+t[rc(x)].val;
}
inline void push_down(int x,int len){
	if(t[x].lazy){
		t[lc(x)].lazy+=t[x].lazy,t[rc(x)].lazy+=t[x].lazy;
		t[lc(x)].val+=(len-(len>>1))*t[x].lazy,t[rc(x)].val+=(len>>1)*t[x].lazy;
		t[x].lazy=0;	
	}
}
void build(int x,int l,int r){
	if(l==r) return t[x].val=a[l],void();
	build(lc(x),l,mid),build(rc(x),mid+1,r),push_up(x);
}
void update(int x,int l,int r,int ul,int ur,int val){
	if(ul<=l&&r<=ur) return t[x].val+=(r-l+1)*val,t[x].lazy+=val,void();
	push_down(x,r-l+1);
	if(ul<=mid) update(lc(x),l,mid,ul,ur,val);
	if(ur>mid) update(rc(x),mid+1,r,ul,ur,val);
	push_up(x);
}
int query(int x,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r) return t[x].val;
	push_down(x,r-l+1);
	int ret=0;
	if(ql<=mid) ret+=query(lc(x),l,mid,ql,qr);
	if(qr>mid) ret+=query(rc(x),mid+1,r,ql,qr);
	return ret;
}
signed main(signed argc, char const *argv[]){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    while(m--){
    	read(opt);
    	if(opt==1) read(l,r,k),update(1,1,n,l,r,k);//更改
    	else if(opt==2) read(k),update(1,1,n,1,1,k);//更改第一个
    	else if(opt==3) read(k),update(1,1,n,1,1,-k);//这个是减法
    	else if(opt==4) read(l,r),put('\n',query(1,1,n,l,r));//查询
    	else put('\n',query(1,1,n,1,1));//查询第一个
	}
    return 0;
}
2020/8/29 18:50
加载中...