[kuangbin带你飞]专题七线段树
你可能会以为自己再按着专题的顺序来进行刷题，但是实则不然，其实我本来想去做做搜索进阶这个专题，结果第一个提的难度就比较坑爹，想了想算了，先写一下线段树吧。其实每个专题都觉得恶心 淦
建议写的时候每个题都要自己去敲，不要直接把模板拿过来改一改
之前写的一个无任何添加剂的模板（甚至连注释都没有） 线段树
@[toc]
HDU 1166 敌兵布阵（线段树单点修改）
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
ll arr[maxn];
ll tree[maxn];
ll add[maxn];
void build_tree(ll node,ll start,ll ends){
if(start==ends) tree[node]=arr[start];
else{
ll mid=(start+ends)/2;
build_tree(2*node,start,mid);
build_tree(2*node+1,mid+1,ends);
tree[node]=tree[2*node]+tree[2*node+1];
}
}
void update_treepoint(ll node ,ll start,ll ends,ll idx,ll val){ //单点修改
if(start==ends){
arr[idx]+=val;
tree[node]+=val;
}
else{
ll mid=(start+ends)/2;
ll left_node=2*node;
ll right_node=2*node+1;
if(idx>=start&&idx<=mid){
update_treepoint(left_node,start,mid,idx,val);
}
else{
update_treepoint(right_node,mid+1,ends,idx,val);
}
tree[node]=tree[left_node]+tree[right_node];
}
}
ll query_tree(ll node,ll start,ll ends,ll l,ll r){
if(start>=l&&ends<=r) return tree[node];
ll mid=(start+ends)/2,ans=0;
if(l<=mid) ans+=query_tree(node*2,start,mid,l,r);
if(r>mid) ans+=query_tree(node*2+1,mid+1,ends,l,r);
return ans;
}
int main()
{
int t;
cin>>t;
int cnt=1;
while(t--){
printf("Case %d:\n",cnt++);
memset(tree,0,sizeof(tree));
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);
build_tree(1,1,n);
string s;
while(cin>>s){
int x,y;
if(s=="End") break;
else if(s=="Query"){
scanf("%d%d",&x,&y);
printf("%lld\n",query_tree(1,1,n,x,y));
}
else if(s=="Add"){
scanf("%d%d",&x,&y);
update_treepoint(1,1,n,x,y);
}
else if(s=="Sub"){
scanf("%d%d",&x,&y);
update_treepoint(1,1,n,x,-y);
}
}
}
}
HDU - 1754（线段树单点修改+区间最大）
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
ll arr[maxn];
ll imax[maxn];
void push_up(ll node){
imax[node]=max(imax[node*2],imax[node*2+1]);
}
void build_tree(ll node,ll start,ll ends){
if(start==ends){
imax[node]=arr[start];
return ;
}
ll mid=(start+ends)/2;
build_tree(2*node,start,mid);
build_tree(2*node+1,mid+1,ends);
push_up(node);
}
void update_treepoint(ll node ,ll start,ll ends,ll idx,ll val){ //单点修改
if(start==ends){
imax[node]=val;
return ;
}
ll mid=(start+ends)/2;
ll left_node=2*node;
ll right_node=2*node+1;
if(idx<=mid) update_treepoint(left_node,start,mid,idx,val);
else update_treepoint(right_node,mid+1,ends,idx,val);
push_up(node);
}
ll tree_max(ll node,ll start,ll ends,ll l,ll r){
if(start>=l&&ends<=r) return imax[node];
ll ans=0;
ll mid=(start+ends)/2;
if(l<=mid) ans=max(ans,tree_max(2*node,start,mid,l,r));
if(r>mid) ans=max(ans,tree_max(2*node+1,mid+1,ends,l,r));
return ans;
}
int main()
{
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);
build_tree(1,1,n);
//for(int i=0;i<100;i++) cout<<imax[i]<<" ";
char c[10];
for(int i=0;i<m;i++){
ll x,y;
scanf("%s",c);
if(c[0]=='Q'){
scanf("%lld%lld",&x,&y);
printf("%lld\n",tree_max(1,1,n,x,y));
}
else{
scanf("%lld%lld",&x,&y);
update_treepoint(1,1,n,x,y);
}
}
}
return 0;
}
POJ - 3468（线段树区间修改+区间求和）
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
ll a[maxn];
ll tree[maxn];
ll add[maxn];
void build(ll node,ll start,ll ends){
if(start==ends){
tree[node]=a[start];
return ;
}
ll mid=(start+ends)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,ends);
tree[node]=tree[2*node]+tree[2*node+1];
}
void Add(ll node,ll start,ll ends,ll val){
add[node]+=val;
tree[node]+=(ends-start+1)*val;
return ;
}
void pushdown(ll node,ll start,ll ends){
if(add[node]==0) return ;
ll mid=(start+ends)/2;
Add(node*2,start,mid,add[node]);
Add(node*2+1,mid+1,ends,add[node]);
add[node]=0;
}
ll query(ll node,ll start,ll ends,ll l,ll r){
if(start>=l&&ends<=r) return tree[node];
ll mid=(start+ends)/2;
ll ans=0;
pushdown(node,start,ends);
if(l<=mid) ans+=query(node*2,start,mid,l,r);
if(mid<r) ans+=query(node*2+1,mid+1,ends,l,r);
return ans;
}
void update(ll node,ll start,ll ends,ll l,ll r,ll val){
if(start>=l&&ends<=r) return Add(node,start,ends,val);
ll mid=(start+ends)/2;
pushdown(node,start,ends);
if(l<=mid) update(2*node,start,mid,l,r,val);
if(r>mid) update(2*node+1,mid+1,ends,l,r,val);
tree[node]=tree[node*2]+tree[node*2+1];
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
//for(int i=1;i<=n;i++) printf("%lld ",tree[i]);
char s[10];
ll x,y,z;
for(int i=0;i<m;i++){
scanf("%s",s);
if(s[0]=='Q'){
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(1,1,n,x,y));
}
else{
scanf("%lld%lld%lld",&x,&y,&z);
update(1,1,n,x,y,z);
}
}
return 0;
}
POJ - 2528（离散化+区间修改）
题解，一开始对这个题也是一头雾水，基本上是没有一点思路。
这里的离散化就是说把很长的海报缩短一点，但又不可以影响其遮挡，这样子的目的其实就是将区间缩短，好用数组储存。
这里只不过区间修改和lazy操作变一下。
如果你要是直接去缩短手抄报的长度，可能会出现一定的问题
兄弟！！！！！！这题我捣鼓了大半天啊啊啊啊啊，终于对了。
来看这篇博客：点我
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int tree[maxn*4];
int lazy[maxn*4];
bool visited[maxn*4];
int cnt=0;
struct wazxy{
int l,r;
}a[maxn];
void init(){
memset(visited,false,sizeof(visited));
memset(lazy,-1,sizeof(lazy));
cnt=0;
}
void pushdowm(int node){
if(lazy[node]!=-1){
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]=-1;
}
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&r>=ends){
lazy[node]=val;
return ;
}
pushdowm(node);
int mid=(start+ends)/2;
if(l<=mid) update(node*2,start,mid,l,r,val);
if(r>mid) update(node*2+1,mid+1,ends,l,r,val);
}
int query(int node,int l,int r){
if(lazy[node]!=-1){
if(visited[lazy[node]]) return 0;
visited[lazy[node]]=true;
return 1;
}
if(r==l) return 0;
int ans=0,mid=(l+r)/2;
ans+=query(node*2,l,mid);
ans+=query(node*2+1,mid+1,r);
return ans;
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
init();
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
tree[++cnt]=a[i].l;
tree[++cnt]=a[i].r;
}
sort(tree+1,tree+1+cnt);
cnt=unique(tree+1,tree+cnt+1)-tree-1;
int m=cnt;
for(int i=2;i<=m;i++){
if(tree[i]-tree[i-1]>1) tree[++cnt]=tree[i-1]+1;
}
sort(tree+1,tree+cnt+1);
for(int i=1;i<=n;i++){
int x=lower_bound(tree+1,tree+1+cnt,a[i].l)-tree;
int y=lower_bound(tree+1,tree+1+cnt,a[i].r)-tree;
//cout<<x<<" "<<y<<endl;
update(1,1,cnt,x,y,i);
}
printf("%d\n",query(1,1,cnt));
}
}
HDU - 1698（线段树只用到一个lazy数组进行储存）
因为每次操作都是要把一个区间变为1或者2或者3，所以通过一个lazy数组储存结果即可
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int lazy[maxn];
void pushdown(int node){
if(lazy[node]){
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]=0;
}
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&ends<=r){
lazy[node]=val;
return ;
}
pushdown(node);
int mid=(start+ends)/2;
if(l<=mid) update(node*2,start,mid,l,r,val);
if(r>mid) update(node*2+1,mid+1,ends,l,r,val);
}
int query(int node,int l,int r){
if(lazy[node]>0){
return lazy[node]*(r-l+1);
}
int ans=0;
int mid=(l+r)/2;
ans+=query(node*2,l,mid);
ans+=query(node*2+1,mid+1,r);
return ans;
}
//int query(int node,int start,int ends,int l,int r){
// if(start>=l&&ends<=r&&lazy[node]>0){
// return lazy[node]*(r-l+1);
// }
// int ans=0;
// int mid=(l+r)/2;
// if(l<=mid) ans+=query(node,start,ends,l,r);
// if(r>mid) ans+=query(node,start,ends,l,r);
// return ans;
//}
int main()
{
int t;
cin>>t;
int z=1;
while(t--){
int n;
scanf("%d",&n);
update(1,1,n,1,n,1);
//printf("Case %d The total value of the hook is %d",z++,query(1,1,n));
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
update(1,1,n,u,v,w);
}
printf("Case %d: The total value of the hook is %d.\n",z++,query(1,1,n));
}
return 0;
}
ZOJ - 1610（线段树+区间修改）
类似于上面的poj2528题。
不过要十分注意一点就是，他这里的表示是区间而不是点
例如1-2之间2-3之间的染***域，而不是点1点2可以染上色。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int lazy[maxn];
int ans[maxn];
int cnt[maxn];
void pushdown(int node){
if(lazy[node]!=-1){
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]=-1;
}
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&ends<=r){
lazy[node]=val;
return ;
}
pushdown(node);
int mid=(start+ends)/2;
if(l<=mid) update(2*node,start,mid,l,r,val);
if(mid<r) update(2*node+1,mid+1,ends,l,r,val);
}
void query(int node,int start,int ends){
if(start==ends){
ans[start]=lazy[node];
return ;
}
pushdown(node);
int mid=(start+ends)/2;
query(node*2,start,mid);
query(node*2+1,mid+1,ends);
}
int main()
{
int n;
while(cin>>n){
memset(lazy,-1,sizeof(lazy));
int x,y,w;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&w);
update(1,1,8000,x+1,y,w);
// query(1,1,8000);
// for(int i=1;i<=10;i++) cout<<ans[i]<<" ";
// cout<<endl;
}
query(1,1,8000);
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=8000;i++)
{
while(ans[i]==ans[i+1]&&i<8000) i++;
if(ans[i]!=-1)
cnt[ans[i]]++;
}
for(int i=0;i<=8000;i++){
if(cnt[i]) printf("%d %d\n",i,cnt[i]);
}
printf("\n");
}
}
POJ - 3264（线段树+最值查询）
第一次写线段树的题目一遍过
怎么说，这个题属于RMQ问题，所以说不仅仅用线段树可以进行求解，线段树只是其中的一个方法，只是原来头节点表示的值是他所有孩子的最大或最小值而已
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000000
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,a[maxn];
int imax,imin;
struct wazxy{
int maxx,minn;
}s[maxn<<2];
void build(int node,int l,int r){
s[node].maxx=MinN;
s[node].minn=MaxN;
if(l==r){
s[node].maxx=s[node].minn=a[l];
return ;
}
int mid=(l+r)>>1;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
s[node].maxx=max(s[node*2].maxx,s[node*2+1].maxx);
s[node].minn=min(s[node*2].minn,s[node*2+1].minn);
}
void query(int node,int start,int ends,int l,int r){
if(start>=l&&ends<=r){
imax=max(imax,s[node].maxx);
imin=min(imin,s[node].minn);
//cout<<imax<<" "<<imin<<endl;
return ;
}
int mid=(start+ends)>>1;
if(l<=mid) query(node*2,start,mid,l,r);
if(mid<r) query(node*2+1,mid+1,ends,l,r);
}
int main()
{
int m,q;
while(cin>>m>>q){
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
}
build(1,1,m);
for(int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
imax=-1e6,imin=1e6;
query(1,1,m,x,y);
//cout<<imax<<" "<<imin<<endl;
printf("%d\n",imax-imin);
}
}
return 0;
}
HDU - 4027（线段树+一个小剪枝）
这个题要注意
剪枝：
维护开根时当子树节点全为1时，无需操作，即该子树的根节点tree等于该子树覆盖长度
当然你们可能不信我减反了导致tle了两个小时
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000000
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
ll tree[maxn];
ll a[maxn];
void build(int node,int l,int r){
if(l==r){
tree[node]=a[l];
return ;
}
ll mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node]=tree[node<<1]+tree[node<<1|1];
}
void push(int node){
tree[node]=tree[node<<1]+tree[node<<1|1];
}
void update(int node,int start,int ends,int l,int r){
if(start==ends){
tree[node]=sqrt(tree[node]);
return ;
}
if(start>=l&&ends<=r&&tree[node]==ends-start+1) return ;
int mid=(start+ends)>>1;
if(l<=mid) update(node<<1,start,mid,l,r);
if(mid<r) update(node<<1|1,mid+1,ends,l,r);
push(node);
}
ll query(int node,int start,int ends,int l,int r){
if(start>=l&&ends<=r){
return tree[node];
}
ll ans=0;
int mid=(start+ends)>>1;
if(l<=mid) ans+=query(node<<1,start,mid,l,r);
if(r>mid) ans+=query(node<<1|1,mid+1,ends,l,r);
return ans;
}
int main()
{
int n;
int z=1;
while(scanf("%d",&n)!=EOF){
printf("Case #%d:\n",z++);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d",&z);
scanf("%d%d",&x,&y);
if(x>y){
int temp=x;
x=y;
y=temp;
}
if(z==0){
//update(x,y,1,n,1);
update(1,1,n,x,y);
}
else{
printf("%lld\n",query(1,1,n,x,y));
}
}
printf("\n");
}
return 0;
}
HDU - 1540(线段树+区间合并模板)⭐⭐⭐
一份不错的题解：点我
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int sum[maxn],pre[maxn],suf[maxn];
int a[maxn];
void pushup(int node,int len){
pre[node]=pre[node<<1];
suf[node]=suf[node<<1|1];
if(pre[node<<1]==(len-(len>>1))) pre[node]=pre[node<<1]+pre[node<<1|1];
if(suf[node<<1|1]==(len>>1)) suf[node]=suf[node<<1]+suf[node<<1|1];
sum[node]=max(suf[node<<1]+pre[node<<1|1],max(sum[node<<1],sum[node<<1|1]));
}
void build(int node,int l,int r){
if(l==r){
sum[node]=pre[node]=suf[node]=1;
return ;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
pushup(node,r-l+1);
}
void update(int node,int start,int ends,int pos,int val){
if(start==ends){
sum[node]=pre[node]=suf[node]=val;
return ;
}
int mid=(start+ends)>>1;
if(pos<=mid) update(node<<1,start,mid,pos,val);
else update(node<<1|1,mid+1,ends,pos,val);
pushup(node,ends-start+1);
}
int query(int node,int start,int ends,int pos){
if(start==ends){
return sum[node];
}
int mid=(start+ends)>>1;
if(pos<=mid){
if(pos+suf[node<<1]>mid) return suf[node<<1]+pre[node<<1|1];
else return query(node<<1,start,mid,pos);
}
else{
if(mid+pre[node<<1|1]>=pos) return pre[node<<1|1]+suf[node<<1];
else return query(node<<1|1,mid+1,ends,pos);
}
}
int main()
{
int n,m;
char s[10];
while(cin>>n>>m){
int x,i=0;
build(1,1,n);
while(m--){
scanf("%s",s);
if(s[0]=='Q'){
scanf("%d",&x);
printf("%d\n",query(1,1,n,x));
}
else if(s[0]=='D'){
scanf("%d",&x);
a[++i]=x;
update(1,1,n,x,0);
}
else{
x=a[i--];
update(1,1,n,x,1);
}
}
}
return 0;
}
HDU - 3974（线段树+dfs序+区间修改+点查询）
首先你需要把所有的关系串联起来，当然dfs是一个非常好用的办法。
穿起来之后就相当于对一个区间进行修改操作了
这样子之后统计一下每个点的开始进入搜索的点编号和从这个点出去的点编号，就可以得到这点如果被更新时，相应的应该更新的所有点的编号都在一个区间内，只需要更新这个区间即可。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 50005
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int tree[maxn<<3];
vector <int> edge[maxn];
int ln[maxn],rn[maxn];
bool visited[maxn];
int num,n;
void init(){
memset(visited,false,sizeof(visited));
memset(tree,-1,sizeof(tree));
memset(ln,-1,sizeof(ln));
memset(rn,-1,sizeof(rn));
for(int i=0;i<maxn;i++) edge[i].clear();
num=1;
}
void pushdown(int node){
if(tree[node]!=-1){
tree[node<<1]=tree[node];
tree[node<<1|1]=tree[node];
tree[node]=-1;
}
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&ends<=r){
tree[node]=val;
return ;
}
pushdown(node);
int mid=(start+ends)>>1;
if(l<=mid) update(node<<1,start,mid,l,r,val);
if(mid<r) update(node<<1|1,mid+1,ends,l,r,val);
}
int query(int node,int start,int ends,int pos){
if(start==ends) return tree[node];
pushdown(node);
int mid=(start+ends)>>1;
if(pos<=mid) query(node<<1,start,mid,pos);
else query(node<<1|1,mid+1,ends,pos);
}
void dfs(int u){
ln[u]=++num;
for(int i=0;i<edge[u].size();i++){
dfs(edge[u][i]);
}
rn[u]=++num;
}
int main()
{
int t;
cin>>t;
int z=1;
char s[10];
while(t--){
init();
cin>>n;
printf("Case #%d:\n",z++);
for(int i=0;i<n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
edge[y].push_back(x);
visited[x]=true;
}
for(int i=1;i<=n;i++){
if(visited[i]==false){
dfs(i);
}
}
int m;
cin>>m;
while(m--){
int x,y;
scanf("%s",s);
if(s[0]=='C'){
scanf("%d",&x);
printf("%d\n",query(1,1,num,rn[x]));
}
else{
scanf("%d%d",&x,&y);
update(1,1,num,ln[x],rn[x],y);
}
}
}
return 0;
}
HDU - 4578（线段树的多种区间操作）
HDU - 4614（线段树+区间更新）
参考博客：点我
每次查询某个区间【X, N】这个区间是否能放一朵花，若能放就返回最后一朵花的位置。若不能放则返回-1。 每次线段树向下递归的时候，判断一下左边空花瓶的数量是否>=f， 若大于代表左边区间的花瓶就可以放完，那么直接递归左边区间，反之则将花的数量-左边区间空花瓶的数量，然后递归右区间。类似主席树求第K大的思想。最后到根节点再判断一下该节点是否能够放花，若不能那么只能又去找另一区间。比如递归了右区间，但是发现右边区间已经无法放了，那么只能去左边区间找最后一朵花的位置。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 50005
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int sum[maxn<<2],lazy[maxn<<2];
void build(int node,int l,int r){
if(l==r){
sum[node]=1;
lazy[node]=-1;
return ;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
lazy[node]=-1;
sum[node]=sum[node<<1]+sum[node<<1|1];
}
void pushdown(int node,int l,int r){
if(lazy[node]==-1) return ;
if(lazy[node]==0){
lazy[node<<1]=lazy[node<<1|1]=0;
sum[node<<1]=sum[node<<1|1]=0;
}
else if(lazy[node]==1){
int mid=(l+r)>>1;
sum[node<<1]=mid-l+1;
sum[node<<1|1]=r-mid;
lazy[node<<1]=lazy[node<<1|1]=1;
}
lazy[node]=-1;
}
void update(int node,int start,int ends,int l,int r,int val){
if(start>=l&&ends<=r){
if(val==1) sum[node]=ends-start+1;
else sum[node]=0;
lazy[node]=val;
return ;
}
int mid=(start+ends)>>1;
pushdown(node,start,ends);
if(l<=mid) update(node<<1,start,mid,l,r,val);
if(mid<r) update(node<<1|1,mid+1,ends,l,r,val);
sum[node]=sum[node<<1]+sum[node<<1|1];
}
int query(int node,int start,int ends,int l,int r){
if(start>=l&&ends<=r) return sum[node];
int mid=(start+ends)>>1;
pushdown(node,start,ends);
int ans=0;
if(l<=mid) ans+=query(node<<1,start,mid,l,r);
if(r>mid) ans+=query(node<<1|1,mid+1,ends,l,r);
return ans;
}
int solve(int node,int start,int ends,int l,int r,int k){
if(start==ends){
if(sum[node]==0) return -1;
if(sum[node]==1) return start;
}
pushdown(node,start,ends);
int ln=0,ans=-1;
int mid=(start+ends)>>1;
if(l<=mid) ln=query(node<<1,start,mid,l,mid);
if(k>ln) ans=solve(node<<1|1,mid+1,ends,l,r,k-ln);
else ans=solve(node<<1,start,mid,l,r,k);
if(ans==-1){
if(ln==0) return -1;
ans=solve(node<<1,start,mid,l,r,k);
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
build(1,1,n);
for(int i=0;i<m;i++){
int x,y,k;
scanf("%d%d%d",&k,&x,&y);
if(k==1){
x++;
int ends=solve(1,1,n,x,n,y);
if(ends==-1) printf("Can not put any one.\n");
else{
int start=solve(1,1,n,x,n,1);
printf("%d %d\n",start-1,ends-1);
update(1,1,n,start,ends,0);
}
}
else{
x++,y++;
int t=query(1,1,n,x,y);
update(1,1,n,x,y,1);
printf("%d\n",y-x-t+1);
}
}
printf("\n");
}
return 0;
}
未完
算法专题学习记录 文章被收录于专栏
一些专题记录
投递蚂蚁集团等公司10个岗位 >
华为工作强度 839人发布
