線分樹テンプレート(NOTONLYSUCCESS神牛)
7396 ワード
NOTONLYSUCCESSブログより、まとめてみました
書き方はとてもふわふわしていて、簡潔です.膜拝.
単点置換、単点増減、区間加算、区間最値
区間置換
区間増減
書き方はとてもふわふわしていて、簡潔です.膜拝.
単点置換、単点増減、区間加算、区間最値
#include
#include
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int MAX[maxn<<2];
int MIN[maxn<<2];
int SUM[maxn<<2];
int max(int a,int b){if(a>b)return a;else return b;}
int min(int a,int b){if(a> 1;
build(lson);
build(rson);
PushUP(rt);
}
void update(int p,int tihuan,int l,int r,int rt)
{
if (l == r) {
MAX[rt] = tihuan;
MIN[rt] = tihuan;
SUM[rt] = tihuan;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(p , tihuan ,lson);
else update(p , tihuan , rson);
PushUP(rt);
}
void update1(int p,int add,int l,int r,int rt)
{
if (l == r) {
SUM[rt] = SUM[rt] + add;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update1(p , add ,lson);
else update1(p , add , rson);
PushUP(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return MAX[rt];
}
int m = (l + r) >> 1;
int ret = -1;
if (L <= m) ret = max(ret , query(L , R , lson));
if (R > m) ret = max(ret , query(L , R , rson));
return ret;
}
int query1(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return MIN[rt];
}
int m = (l + r) >> 1;
int ret = 99999;
if (L <= m) ret = min(ret , query1(L , R , lson));
if (R > m) ret = min(ret , query1(L , R , rson));
return ret;
}
int queryhe(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return SUM[rt];
}
int m = (l + r) >> 1;
int ret = 0;
if (L <= m) ret += queryhe(L , R , lson);
if (R > m) ret += queryhe(L , R , rson);
return ret;
}
int main()
{
int n , m;
while (~scanf("%d%d",&n,&m))
{
build(1 , n , 1);
while (m --) {
char op[2];
int a , b;
scanf("%s%d%d",op,&a,&b);
if (op[0] == 'Q') //
{
/* for(int i = 1;i<=10;i++)
printf("%d ",MAX[i]);
puts("");*/
printf("%d
",query(a , b , 1 , n , 1));
}
else if(op[0]=='U') //
update(a , b , 1 , n , 1);
else if(op[0]=='M')//
{
/*for(int i = 1;i<=10;i++)
printf("%d ",MIN[i]);
puts("");*/
printf("%d
",query1(a , b , 1 , n , 1));
}
else if(op[0]=='H')//
{
printf("%d
",queryhe(a , b , 1 , n , 1));
}
else if(op[0]=='S')//
{
scanf("%d%d",&a,&b);
update1(a , b , 1 , n , 1);
}
else if(op[0]=='E')//
{
scanf("%d%d",&a,&b);
update1(a , -b , 1 , n , 1);
}
}
}
return 0;
}
区間置換
#include
#include
#include
#include
#include
#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
const int maxn = 100100;
using namespace std;
int lazy[maxn<<2];
int sum[maxn<<2];
void PushUp(int rt)// 、
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt,int m) //
{
if (lazy[rt]) //
{
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
sum[rt<<1] = (m - (m >> 1)) * lazy[rt];
sum[rt<<1|1] = ((m >> 1)) * lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt)//
{
lazy[rt] = 0;
if (l== r)
{
scanf("%d",&sum[rt]);
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt)//
{
//if(L>l||R>r) return;
if (L <= l && r <= R)
{
lazy[rt] = c;
sum[rt] = c * (r - l + 1);
//printf("%d %d %d %d %d
", rt, sum[rt], c, l, r);
return ;
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L , R , c , lson);
if (R > m) update(L , R , c , rson);
PushUp(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
//printf("%d
", sum[rt]);
return sum[rt];
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
LL ret = 0;
if (L <= m) ret += query(L , R , lson);
if (m < R) ret += query(L , R , rson);
return ret;
}
int main()
{
int n , m;
char str[5];
while(scanf("%d%d",&n,&m))
{
build(1 , n , 1);
while (m--)
{
scanf("%s",str);
int a , b , c;
if(str[0]=='T')
{
scanf("%d%d%d",&a,&b,&c);
update(a , b , c , 1 , n , 1);
}
else if(str[0]=='Q')
{
scanf("%d%d",&a,&b);
cout< 区間増減
#include
#include
#include
#include
#include
#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL __int64
const int maxn = 100100;
using namespace std;
LL lazy[maxn<<2];
LL sum[maxn<<2];
void putup(int rt)
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void putdown(int rt,int m)
{
if (lazy[rt])
{
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt] * (m - (m >> 1));
sum[rt<<1|1] += lazy[rt] * (m >> 1);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt) {
lazy[rt] = 0;
if (l == r)
{
scanf("%I64d",&sum[rt]);
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
putup(rt);
}
void update(int L,int R,int c,int l,int r,int rt)
{
if (L <= l && r <= R)
{
lazy[rt] += c;
sum[rt] += (LL)c * (r - l + 1);
return ;
}
putdown(rt , r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L , R , c , lson);
if (m < R) update(L , R , c , rson);
putup(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return sum[rt];
}
putdown(rt , r - l + 1);
int m = (l + r) >> 1;
LL ret = 0;
if (L <= m) ret += query(L , R , lson);
if (m < R) ret += query(L , R , rson);
return ret;
}
int main()
{
int n , m;int a , b , c;
char str[5];
scanf("%d%d",&n,&m);
build(1 , n , 1);
while (m--)
{
scanf("%s",str);
if (str[0] == 'Q')
{
scanf("%d%d",&a,&b);
printf("%I64d
",query(a , b , 1 , n , 1));
}
else if(str[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
update(a , b , c , 1 , n , 1);
}
}
return 0;
}