求助线段树
查看原帖
求助线段树
360930
Jairon314楼主2021/8/7 22:53

刚学指针版的线段树,写完一遍过了样例以后正常开 long long 就输出乱码?

下面是没开 long long 的,能正常过样例

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define $int long long

/***************快读***************/

namespace IO {
char buf[1<<21], *p1 = buf, *p2 = buf, buf1[1<<21];
inline char gc () {return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}

#ifndef ONLINE_JUDGE
#endif

#define gc getchar

template<class I>
inline void read(I &x) {
    x = 0; I f = 1; char c = gc();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc(); }
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = gc(); }
    x *= f;
}

template<class I>
inline void write(I x) {
    if(x == 0) {putchar('0'); return;}
    I tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while(cnt > 0) putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO;

/***************快读***************/

#define maxn 1000010

int a[maxn];
int n,m;
int opt,l,r;
int val;

class Segment_Tree{
	protected:

	public:
		struct Seg_Tree{
			int l,r;
			int val;
			int len;
			int lazy;
			Seg_Tree *lson, *rson;
			Seg_Tree(){lson=rson=NULL;}
		} *root;

		void pushup(Seg_Tree *rt){
			rt->val=(rt->lson)->val+(rt->rson)->val;
		}

		void build(Seg_Tree *rt,int l,int r){
			rt->l=l,rt->r=r;
			rt->len=(r-l+1);
			if(l==r){
				rt->val=a[l];
				return;
			}
			int mid=(l+r)>>1;
			rt->lson=new Seg_Tree();
			rt->rson=new Seg_Tree();
			build(rt->lson,l,mid);
			build(rt->rson,mid+1,r);
			pushup(rt);
		}

		void pushdown(Seg_Tree *rt){
			if((rt->l)==(rt->r)){return;}
			(rt->lson)->lazy+=rt->lazy;
			(rt->rson)->lazy+=rt->lazy;
			(rt->lson)->val+=((rt->lson)->len)*(rt->lazy);
			(rt->rson)->val+=((rt->rson)->len)*(rt->lazy);
			(rt->lazy)=0;
		}

		void update(Seg_Tree *rt,int l,int r,int val){
			if((rt->l)>=l&&(rt->r)<=r){
				(rt->lazy)+=val;
				(rt->val)+=(rt->len)*val;
				return;
			}
			pushdown(rt);
			if((rt->lson)!=NULL&&l<=(rt->lson)->r){update((rt->lson),l,r,val);}
			if((rt->rson)!=NULL&&r>=(rt->rson)->l){update((rt->rson),l,r,val);}
			pushup(rt);
			return;
		}

		int query(Seg_Tree *rt,int l,int r){
			if((rt->l)>=l&&(rt->r)<=r){
				return (rt->val);
			}
			pushdown(rt);
			int ans=0;
			if((rt->lson)!=NULL&&l<=(rt->lson)->r){ans+=query((rt->lson),l,r);}
			if((rt->rson)!=NULL&&r>=(rt->rson)->l){ans+=query((rt->rson),l,r);}
			// pushup(rt);
			return ans;
		}

		void init(){
			root=new Seg_Tree();
			build(root,1,n);
		}
}se;

int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){read(a[i]);}
	se.init();
	while(m--){
		read(opt);
		switch(opt){
			case 1:
				read(l),read(r),read(val);
				se.update(se.root,l,r,val);
				break;
			case 2:
				read(l),read(r);
				outn(se.query(se.root,l,r));
				break;
		}
	}
	return 0;
}

下面是开了 long long 的,过不了样例,还输出一堆乱码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define $int long long

/***************快读***************/

namespace IO {
char buf[1<<21], *p1 = buf, *p2 = buf, buf1[1<<21];
inline char gc () {return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}

#ifndef ONLINE_JUDGE
#endif

#define gc getchar

template<class I>
inline void read(I &x) {
    x = 0; I f = 1; char c = gc();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc(); }
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = gc(); }
    x *= f;
}

template<class I>
inline void write(I x) {
    if(x == 0) {putchar('0'); return;}
    I tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while(cnt > 0) putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO;

/***************快读***************/

#define maxn 1000010

$int a[maxn];
int n,m;
int opt,l,r;
$int val;

class Segment_Tree{
	protected:

	public:
		struct Seg_Tree{
			int l,r;
			$int val;
			int len;
			$int lazy;
			Seg_Tree *lson, *rson;
			Seg_Tree(){lson=rson=NULL;}
		} *root;

		void pushup(Seg_Tree *rt){
			rt->val=(rt->lson)->val+(rt->rson)->val;
		}

		void build(Seg_Tree *rt,int l,int r){
			rt->l=l,rt->r=r;
			rt->len=(r-l+1);
			if(l==r){
				rt->val=a[l];
				return;
			}
			int mid=(l+r)>>1;
			rt->lson=new Seg_Tree();
			rt->rson=new Seg_Tree();
			build(rt->lson,l,mid);
			build(rt->rson,mid+1,r);
			pushup(rt);
		}

		void pushdown(Seg_Tree *rt){
			if((rt->l)==(rt->r)){return;}
			(rt->lson)->lazy+=rt->lazy;
			(rt->rson)->lazy+=rt->lazy;
			(rt->lson)->val+=1ll*((rt->lson)->len)*(rt->lazy);
			(rt->rson)->val+=1ll*((rt->rson)->len)*(rt->lazy);
			(rt->lazy)=0;
		}

		void update(Seg_Tree *rt,int l,int r,int val){
			if((rt->l)>=l&&(rt->r)<=r){
				(rt->lazy)+=val;
				(rt->val)+=1ll*(rt->len)*val;
				return;
			}
			pushdown(rt);
			if((rt->lson)!=NULL&&l<=(rt->lson)->r){update((rt->lson),l,r,val);}
			if((rt->rson)!=NULL&&r>=(rt->rson)->l){update((rt->rson),l,r,val);}
			pushup(rt);
			return;
		}

		$int query(Seg_Tree *rt,int l,int r){
			if((rt->l)>=l&&(rt->r)<=r){
				return (rt->val);
			}
			pushdown(rt);
			$int ans=0ll;
			if((rt->lson)!=NULL&&l<=(rt->lson)->r){ans+=query((rt->lson),l,r);}
			if((rt->rson)!=NULL&&r>=(rt->rson)->l){ans+=query((rt->rson),l,r);}
			// pushup(rt);
			return ans;
		}

		void init(){
			root=new Seg_Tree();
			build(root,1,n);
		}
}se;

int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){read(a[i]);}
	se.init();
	while(m--){
		read(opt);
		switch(opt){
			case 1:
				read(l),read(r),read(val);
				se.update(se.root,l,r,val);
				break;
			case 2:
				read(l),read(r);
				outn(se.query(se.root,l,r));
				break;
		}
	}
	return 0;
}
2021/8/7 22:53
加载中...