9.1 线段树 P4145 上帝造题的七分钟2 / 花神游历各国
资料：
https://blog.csdn.net/WhereIsHeroFrom/article/details/78969718
https://www.cnblogs.com/cjyyb/p/8567674.html
https://www.cnblogs.com/cjyyb/p/8567721.html
P4145 上帝造题的七分钟2 / 花神游历各国
/*
translation:
第三行一个整数m，表示有m次操作。
k=0表示给[l,r]中的每个数开平方(下取整)
k=1表示询问[l,r]中各个数的和。
数据中有可能l>r所以遇到这种情况请交换l和r。
solution:
唯一的考点，就是在如何取根号上，由于期间信息无法快速更新，所以无法使用延迟标记lazytag
（哦，这太可怕了QAQ），所以大家都注意到了10^9最多开5次就不变了，所以我们可以
考虑每次把修改暴力递归下去，直到当前区间已经全是0或1为止，然后return就好了。
似乎这题目前只有这一种解法，所以说不是非常的新鲜，本题解主要就是记录一种思想和历程，
学习一种结构，一定要搞清楚原理后再回头看看，有时候会柳暗花明又一村
喏 ,code is below.
trigger:
“下去整 ” ,最最重要的优化就是maxx>1才change
区间修改，区间查询，but，无结合律性质
note:
*暴力线段树 ,无法搞lazy_tag ，所以没有pushdown,f的操作
date:
2019.08.15
2019.09.01
*/
#define lson o<<1
#define rson o<<1|1
#define N 1000005
int n,m;
int a[N];
struct tree{
int l,r;
int sum,maxx;//maxx表示最高次幂
}t[N<<2];
inline void pushup(int o){
t[o].sum=t[lson].sum+t[rson].sum;
t[o].maxx=max(t[lson].maxx,t[rson].maxx);
}
inline void build(int l,int r,int o){
t[o].l=l,t[o].r=r;
if(l==r){
t[o].sum=t[o].maxx=a[l];
return ;
}
int mid=t[o].l+t[o].r>>1;
build(l,mid,lson);
build(mid+1,r,rson);
pushup(o);
}
inline void change(int o,int x,int y){
if(t[o].l==t[o].r){
t[o].sum=t[o].maxx=sqrt(t[o].sum);
return ;
}
int mid=t[o].l+t[o].r>>1;
if(x<=mid && t[lson].maxx>1)change(lson,x,y);
if(mid<y && t[rson].maxx>1)change(rson,x,y);
pushup(o);
}
inline int query(int o,int x,int y){
if(x<=t[o].l && t[o].r<=y){
return t[o].sum;
}
int ans=0;
int mid=t[o].l+t[o].r>>1;
if(x<=mid)ans+=query(lson,x,y);
if(mid<y)ans+=query(rson,x,y);
return ans;
}
#undef int
int main(){
#define int long long
freopen("huashen.txt","r",stdin);
rd(n);
rep(i,1,n)rd(a[i]);
build(1,n,1);
rd(m);
while(m--){
int op,l,r;rd(op),rd(l),rd(r);
if(l>r)swap(l,r);
if(op==0)change(1,l,r);
else printf("%d
",query(1,l,r));
}
return 0;
}
线段树1 板子
/*
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
*/
#define lson o<<1
#define rson o<<1|1
#define N 100010
int a[N];
struct tree{
int l,r;
int sum,add;
}t[N<<2];
inline void pushup(int o){t[o].sum=t[lson].sum+t[rson].sum;}
inline void f(int delta,int o){
t[o].add+=delta;
t[o].sum+=delta*(t[o].r-t[o].l+1);
}
inline void pushdown(int o){
if(t[o].add==0)return;
f(t[o].add,lson);
f(t[o].add,rson);
t[o].add=0;
}
inline void update(int o,int x,int y,int k){
if(x<=t[o].l && t[o].r<=y){
f(k,o);
return ;
}
pushdown(o);
int mid=t[o].l+t[o].r>>1;
if(x<=mid)update(lson,x,y,k);
if(mid<y)update(rson,x,y,k);
pushup(o);
}
inline int query(int o,int x,int y){
if(x<=t[o].l && t[o].r<=y){
return t[o].sum;
}
pushdown(o);
int mid=t[o].l+t[o].r>>1;
int ans=0;
if(x<=mid)ans+=query(lson,x,y);
if(mid<y)ans+=query(rson,x,y);
return ans;
}
inline void build(int l,int r,int o){
t[o].l=l,t[o].r=r;
if(l==r){
t[o].sum=a[l];
return ;
}
int mid=l+r>>1;
build(l,mid,lson);
build(mid+1,r,rson);
pushup(o);
}
#undef int
int main(){
#define int long long
//freopen("sgm1.txt","r",stdin);
int n,m;rd(n),rd(m);
rep(i,1,n)rd(a[i]);
build(1,n,1);
while(m--){
char op[3];
int x,y,k;
cin>>op;
if(op[0]=='C'){
rd(x),rd(y),rd(k);
update(1,x,y,k);
}
else if(op[0]=='Q'){
rd(x),rd(y);
printf("%lld
",query(1,x,y));
}
}
return 0;
}
区间最大连续子段和
#define lson o<<1
#define rson o<<1|1
#define N 500001
int max_3(int a,int b,int c){
int d=a;
if(b>d)d=b;
if(c>d)d=c;
return d;
}
struct tree{
int l,r;
int lmax,rmax,sum,dat;
}t[N<<2];
inline void pushup(int o){
t[o].lmax=max_3(t[lson].sum,t[lson].sum+t[rson].lmax,t[lson].lmax);
t[o].rmax=max_3(t[rson].sum,t[rson].sum+t[lson].rmax,t[rson].rmax);
t[o].dat=max_3(t[lson].dat,t[rson].dat,t[lson].rmax+t[rson].lmax);
t[o].sum=t[lson].sum+t[rson].sum;
}
inline void build(int l,int r,int o){
t[o].l=l,t[o].r=r;
if(l==r){
rd(t[o].dat);
t[o].sum=t[o].lmax=t[o].rmax=t[o].dat;
return ;
}
int m=t[o].l+t[o].r>>1;
build(l,m,lson);
build(m+1,r,rson);
pushup(o);
}
inline void change(int o,int x,int v){
if(t[o].l==t[o].r){
t[o].sum=t[o].lmax=t[o].rmax=t[o].dat=v;
return ;
}
int m=t[o].l+t[o].r>>1;
if(x<=m)change(lson,x,v);
else change(rson,x,v);
pushup(o);
}
tree query(int o,int l,int r){
if(t[o].l==l && t[o].r==r){
return t[o];
}
int m=t[o].l+t[o].r>>1;
if(r<=m)return query(lson,l,r);
else if(m<l)return query(rson,l,r);
else{
tree ls=query(lson,l,m);
tree rs=query(rson,m+1,r);
tree ans;
ans.dat=max_3(ls.dat,rs.dat,ls.rmax+rs.lmax);
ans.lmax=max_3(ls.sum,ls.lmax,ls.sum+rs.lmax);
ans.rmax=max_3(rs.sum,rs.rmax,rs.sum+ls.rmax);
ans.sum=ls.sum+rs.sum;
return ans;
}
}
#undef int
int main(){
#define int long long
freopen("CH4301.txt","r",stdin);
int n,m;rd(n),rd(m);
build(1,n,1);
while(m--){
int op,x,y,v;
rd(op);
if(op==1){
rd(x),rd(y);
if(x>y)swap(x,y);
tree ans=query(1,x,y);
printf("%lld
",ans.dat);
}
else{
rd(x),rd(v);
change(1,x,v);
}
}
return 0;
}
/*
题目描述
给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和
2、“2 x y”，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
对于每个查询指令输出一个整数表示答案。
N≤500000,M≤100000
N≤500000,M≤100000
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
sol:
对于一个固定区间，求最大子段和我们有O(n)
的算法。但是如何维护不同区间的LIS
就成了一个问题。我们选择线段树解决区间问题，但使用线段树的话，我们需要明白，维护什么值，以
及如何进行区间操作。
那么我们思考，对于相邻的两个区间，他们的LIS
有几种可能？
1.左侧区间的LIS
2.右侧区间的LIS
3.两个区间合并后，中间新连接的部分
前两点都好理解，针对第三点我们继续思考，中间部分能够成为LIS，其实就是我们从连接部分分别向前向后，获
得一个尽可能大的前/后缀和。那么我们维护或者合并区间的LIS
就需要维护三个值，区间最大子段和，最大前缀和，最大后缀和。而我们在合并区间的时候，如何维护前/后缀和呢？
我们需要多维护一个区间和。
整理我们得到，定义区间ls,rs
合并得到区间d，每个区间维护区间和sum
，区间最大字段和maxs
，区间最大前缀和maxl
，区间最大后缀和maxr
。则合并区间时，可得关系如下
d.sum=ls.sum+rs.sum
d.maxs=max(ls.maxs,rs.maxs,ls.maxr+rs.maxl)
d.maxl=max(ls.maxl,ls.sum+rs.maxl)
d.maxr=max(rs.maxr,rs.sum+ls.maxr)
用线段树维护即可
*/
区间查询最大值，单点修改
/*
reference:
translation:
solution:
trigger:
note:
*
record:
date:
2019.09.01
*/
#define N 200010
#define lson o<<1
#define rson o<<1|1
struct tree{
int l,r;
int maxx;
}t[N<<2];
int n,m;
int a[N];
inline void pushup(int o){
t[o].maxx=max(t[lson].maxx,t[rson].maxx);
}
inline void change(int o,int x,int v){
if(t[o].l==t[o].r){
if(t[o].maxx<v)
t[o].maxx=v;
return ;
}
int mid=t[o].l+t[o].r>>1;
if(x<=mid)change(lson,x,v);//在左子树
else change(rson,x,v);//在右子树
pushup(o);
}
inline void build(int l,int r,int o){
t[o].l=l,t[o].r=r;
if(l==r){
t[o].maxx=a[l];
return;
}
int mid=l+r>>1;
build(l,mid,lson);
build(mid+1,r,rson);
pushup(o);
}
inline int query(int o,int x,int y){
if(x<=t[o].l && t[o].r<=y){
return t[o].maxx;
}
int val=-(1<<30);
int mid=t[o].l+t[o].r>>1;
if(x<=mid)val=max(val,query(lson,x,y));
if(mid<y)val=max(val,query(rson,x,y));
return val;
}
int main(){
#ifdef WIN32
freopen("","r",stdin);
#endif
rd(n),rd(m);
rep(i,1,n)rd(a[i]);
build(1,n,1);
while(m--){
char op[3];int x,y,v;
cin>>op;
if(op[0]=='Q'){
rd(x),rd(y);
printf("%d
",query(1,x,y));
}
else if(op[0]=='U'){
rd(x),rd(v);
change(1,x,v);
}
}
return 0;
}
区间最大公约数
reference:https://www.acwing.com/solution/acwing/content/1047/
#define N 500010
#define lson o<<1
#define rson o<<1|1
struct tree{
int l,r,dat;
}t[N<<2];
int a[N],cf[N],tr[N];
int n,m;
inline void pushup(int o){
t[o].dat=__gcd(t[lson].dat,t[rson].dat);
}
inline void build(int l,int r,int o){
t[o].l=l,t[o].r=r;
if(l==r){
t[o].dat=cf[l];
return ;
}
int mid=l+r>>1;
build(l,mid,lson);
build(mid+1,r,rson);
pushup(o);
}
inline void update(int o,int x,int v){
if(x>n)return ;/////////////////////////////////
if(t[o].l==t[o].r){
t[o].dat+=v;
return ;
}
int mid=(t[o].l+t[o].r)>>1;
if(x<=mid)update(lson,x,v);
else update(rson,x,v);
pushup(o);
}
inline int ask(int o,int x,int y){
if(x>y)return 0;///////////////////////////////////////
if(x<=t[o].l && t[o].r<=y){
return abs(t[o].dat);
}
int mid=t[o].l+t[o].r>>1;
int gcd_l=0,gcd_r=0;
if(x<=mid)gcd_l=ask(lson,x,y);
if(mid<y)gcd_r=ask(rson,x,y);
return abs(__gcd(gcd_l,gcd_r));
}
inline void add(int x, int k){
for(int i=x;i<=n;i+=(-i)&i)
tr[i]+=k;
}
inline int query(int x){
int ans=0;
for(int i=x;i;i-=(-i)&i)
ans+=tr[i];
return ans;
}
#undef int
int main(){
#define int long long
rd(n),rd(m);
rep(i,1,n){
rd(a[i]);
cf[i]=a[i]-a[i-1];
}
build(1,n,1);
while(m--){
int x,y,k;
char op[5];scanf("%s",&op);
if(op[0]=='Q'){
rd(x),rd(y);
printf("%lld
",__gcd(a[x]+query(x),ask(1,x+1,y)));
}
else{
rd(x),rd(y),rd(k);
update(1,x,k);
update(1,y+1,-k);
add(x,k);
add(y+1,-k);
}
}
return 0;
}