刚学指针版的线段树,写完一遍过了样例以后正常开 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;
}