【HAOI2013】软件安装

  • 本文为博主原创，未经许可不得转载

这道题一眼线段树，秒水题真是爽啊

然而还是调了2个小时。。。。。。

我们只需要用线段树维护lx,rx,maxx，分别表示区间的左起连续0的个数，右起连续的0的个数，最大的连续0的个数，就可以实现区间信息的合并。

坑点：标记必须提前下传，因为回答询问时需要用到子节点信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "read"
#define MAXN 50010
using namespace std;
struct node{int lx,rx,maxx,tag;}tr[MAXN<<3];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft)?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
void relord(int p,int l,int r){
	if(tr[p].tag==0)  tr[p].lx=tr[p].rx=tr[p].maxx=r-l+1;
	else if(tr[p].tag==1)  tr[p].lx=tr[p].rx=tr[p].maxx=0;
}
void pushdown(int p,int l,int r){
	if(tr[p].tag==-1)  return;
	int mid=(l+r)>>1;
	tr[p<<1].tag=tr[p<<1|1].tag=tr[p].tag;
	relord(p<<1,l,mid);  relord(p<<1|1,mid+1,r);
	tr[p].tag=-1;
}
void pushup(int p,int l,int r){
	tr[p].maxx=max(tr[p<<1].maxx,max(tr[p<<1|1].maxx,tr[p<<1].rx+tr[p<<1|1].lx));
	int mid=(l+r)>>1;
	if(tr[p<<1].lx==mid-l+1)  tr[p].lx=tr[p<<1].lx+tr[p<<1|1].lx;
	else tr[p].lx=tr[p<<1].lx;
	if(tr[p<<1|1].rx==r-mid)  tr[p].rx=tr[p<<1|1].rx+tr[p<<1].rx;
	else tr[p].rx=tr[p<<1|1].rx;
}
int ask(int p,int l,int r,int x){
	pushdown(p,l,r);
	if(l==r)  return l;  
	int mid=(l+r)>>1; 
	if(tr[p<<1].maxx>=x)  return ask(p<<1,l,mid,x);
	if(tr[p<<1].rx+tr[p<<1|1].lx>=x)  return mid-tr[p<<1].rx+1;
	return ask(p<<1|1,mid+1,r,x);
}
void updata(int p,int l,int r,int x,int y,int v){
	pushdown(p,l,r);
	if(x<=l&&y>=r)  {tr[p].tag=v; relord(p,l,r); return;}
	int mid=(l+r)>>1; 
	if(mid>=y)  updata(p<<1,l,mid,x,y,v);  
    else if(mid<x)  updata(p<<1|1,mid+1,r,x,y,v);  
    else{  
        updata(p<<1,l,mid,x,mid,v);  
        updata(p<<1|1,mid+1,r,mid+1,y,v);  
    }  	
	pushup(p,l,r);
}
void build(int p,int l,int r){
	pushdown(p,l,r);
	if(l==r)  return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);  build(p<<1|1,mid+1,r);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read(),m=read();  relord(1,1,n);  build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt=read(),x=read();
		if(opt==1){
			if(tr[1].maxx>=x){
				int t=ask(1,1,n,x);
				updata(1,1,n,t,t+x-1,1);
				printf("%d\n",t);
			}
			else puts("0");
		}
		else{int y=read();updata(1,1,n,x,x+y-1,0);}
	}
	return 0;
}

本文标题:【HAOI2013】软件安装

文章作者:chty

发布时间:2017年03月20日 - 20时52分

最后更新:2018年03月02日 - 17时31分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,