A

Segment with the Maximum Sum

题意：给定长度为n的数组，查询最大子段和。每次操作将下标为i的改成v

思路：线段树维护sum,lmax,rmax,tmax：区间和，区间最大前缀和，区间最大后缀和，区间最大子段和。

如何维护父节点的区间最大前缀和：

（1）左儿子的最大前缀和

（2）左儿子的区间和+右儿子的最大前缀和

如何维护父节点的区间最大后缀和：

（1）右儿子的最大后缀和

（2）右儿子的区间和+左儿子的最大前缀和

如何维护父节点最大子段和：

（1）左儿子的最大子段和

（2）右儿子的最大子段和

（3）左儿子的最大后缀和+右儿子的最大前缀和

#include 
#define ios cin.sync_with_stdio(false)
#define PII pair
#define int long long
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
struct node{int l,r;ll sum;ll lmax,rmax,tmax;
}tr[N*4];
void pushup(int u)
{node &root=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];root.sum=l.sum+r.sum;root.lmax=max(l.lmax,l.sum+r.lmax);root.rmax=max(r.rmax,r.sum+l.rmax);root.tmax=max({l.tmax,r.tmax,l.rmax+r.lmax});
}
void build(int u,int l,int r)
{if(l==r) tr[u]={l,r,a[l],a[l],a[l],a[l]};else {tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].tmax;else{int mid=tr[u].l+tr[u].r>>1;int ans=0;if(l<=mid) ans=max(ans,query(u<<1,l,r));if(r>=mid+1) ans=max(ans,query(u<<1|1,l,r));return ans;}
}
void modify(int u,int x,int v)
{if(tr[u].l==x&&tr[u].r==x) tr[u]={x,x,v,v,v,v};else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}
void solve()
{cin>>n>>m;for(int i=0;i>a[i];build(1,0,n-1);cout<>x>>v;modify(1,x,v);cout<>_t;while(_t--) solve();system("pause");return 0;
}

B

K-th one

题意：给定长度为n的数组，数组元素只能取值0或1。m次操作，

操作1：下标为i的元素取反

操作2：查询第k个1的位置（注意：1个数从0开始编号）

思路：线段树存储区间和。查询时，若左儿子的区间和>=k，那么递归查询左儿子；否则递归查询右儿子，在递归时需要让k减去左儿子的区间和。

#include 
#define ios cin.sync_with_stdio(false)
#define PII pair
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
struct node{int l,r;int sum;
}tr[N*4];
void pushup(int u)
{tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{if(l==r) tr[u]={l,r,a[l]};else{tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int x)
{if(tr[u].l==tr[u].r) tr[u].sum^=1;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x);else modify(u<<1|1,x);pushup(u);}
}
int query(int u,int x)
{if(tr[u].l==tr[u].r) return tr[u].l;else{int mid=tr[u].l+tr[u].r>>1;if(tr[u<<1].sum>=x) return query(u<<1,x);else return query(u<<1|1,x-tr[u<<1].sum);}
}
void solve()
{cin>>n>>m;for(int i=0;i>a[i];build(1,0,n-1);while(m--){int op,x;cin>>op>>x;if(op==1) modify(1,x);else cout<>_t;while(_t--) solve();system("pause");return 0;
}

C

First element at least X

题意：给定长度为n的数组，m次操作，

操作1：下标为i的元素改成v

操作2：查询第1个大于等于x的位置（注意：从0开始编号）,不存在输出-1.

思路：线段树存储区间最大值。查询时，若左儿子的区间最大值>=x，那么递归查询左儿子；否则递归查询右儿子。叶子节点判断是否大于等于x，不满足返回-1

#include 
#define ios cin.sync_with_stdio(false)
#define PII pair
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
struct node{int l,r;int ma;
}tr[N*4];
void pushup(int u)
{tr[u].ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
}
void build(int u,int l,int r)
{if(l==r) tr[u]={l,r,a[l]};else{tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int x,int v)
{if(tr[u].l==tr[u].r) tr[u].ma=v;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}
int query(int u,int x)
{if(tr[u].l==tr[u].r) {if(tr[u].ma>=x) return tr[u].l;else return -1;}else{int mid=tr[u].l+tr[u].r>>1;if(tr[u<<1].ma>=x) return query(u<<1,x);else return query(u<<1|1,x);}
}
void solve()
{cin>>n>>m;for(int i=0;i>a[i];build(1,0,n-1);while(m--){int op;cin>>op;if(op==1){int x,v;cin>>x>>v;modify(1,x,v);}else {int x;cin>>x;cout<>_t;while(_t--) solve();system("pause");return 0;
}

D

First element at least X - 2

题意：给定长度为n的数组，m次操作，

操作1：下标为i的元素改成v

操作2：给定x和l，查询下标j，满足j>=l && a[j]>=x,不存在输出-1.

思路：线段树存储区间最大值。查询时，若左儿子的区间最大值>=x && mid>=l，那么递归查询左儿子；否则或者左儿子无解时 ，递归查询右儿子。叶子节点判断是否大于等于x，下标是否大于等于l，不满足返回-1

#include 
#define ios cin.sync_with_stdio(false)
#define PII pair
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
struct node{int l,r;int ma;
}tr[N*4];
void pushup(int u)
{tr[u].ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
}
void build(int u,int l,int r)
{if(l==r) tr[u]={l,r,a[l]};else{tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int x,int v)
{if(tr[u].l==tr[u].r) tr[u].ma=v;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}
}
int query(int u,int x,int l)
{if(tr[u].l==tr[u].r) {if(tr[u].ma>=x&&tr[u].l>=l) return tr[u].l;else return -1;}else{int mid=tr[u].l+tr[u].r>>1;int ans=-1;if(tr[u<<1].ma>=x&&mid>=l) ans=query(u<<1,x,l);if(ans==-1) ans=query(u<<1|1,x,l);return ans;}
}
void solve()
{cin>>n>>m;for(int i=0;i>a[i];build(1,0,n-1);while(m--){int op;cin>>op;if(op==1){int x,v;cin>>x>>v;modify(1,x,v);}else {int x,l;cin>>x>>l;cout<>_t;while(_t--) solve();system("pause");return 0;
}