郑轻校赛的抢钱题,第6题到第7题的坎,或者做另外一个弱不会的网络流

比赛的时候知道是线段树,但是没有完全理解线段树lazy标记是干啥,所以呢,写了一个每次都传递到底的线段树,实质上比暴力还慢


线段树:为了查询和插入删除操作更加均衡的数据结构,时间都是O(logn)

网上有很多学习链接,其实质是一个节点代表一个区间的值,通常的用法是数组的第一个值a[1]表示整个区间的状态,然后依次二分,根据题意定义节点状态


如n=10个节点的线段树

a[1]:负责1-10区间

a[2]:负责1-5区间

a[3]:负责6-10区间

a[4]:负责1-3区间

a[5]:负责4-5区间

a[6]:负责6-8区间

a[7]:负责9-10区间

a[8]:负责1-2区间

a[9]:负责3区间(单个节点的区间)

a[10]:负责4区间(单个节点的区间)

a[11]:负责5区间(单个节点的区间)

a[12]:负责6-7区间

a[13]:负责8区间(单个节点的区间)

a[14]:负责9区间(单个节点的区间)

a[15]:负责10区间(单个节点的区间)

a[16]:负责1区间(单个节点的区间)

a[17]:负责2区间(单个节点的区间)

空了a[18],a[19],a[20],a[21],a[22],a[23]

a[24]:负责6区间(单个节点的区间)

a[25]:负责7区间(单个节点的区间)


原理:每次二分线段长度,若为奇数左边长1,数组标号左儿子*2,右儿子*2+1,直到将区间都分割成了小区间(端点)为止

(文字描述很枯燥,大家画个图就懂了)


lazy原理:当线段树传递标记的时候,每次都往最下面走复杂度稳定为O(logn)没有必要

比如说郑轻这个题:把所有的线段放进去,查询线段中各个点最小值是否不小于2,若是则符合,否则不取

题目链接:我是lazy线段树


我需要操作:当前这个线段访问次数+1

当这个线段访问次数+1的时候,那么其子线段自增1是肯定的,如果现在直接往下传递很浪费时间,不妨另取个数组,标记下这个节点访问次数+1(lazy标记当不得不下放的时候下方)

例子:仍取n=10,操作[3,5]这个区间连续2次

如果是直接往下传递,那么更新了3,4&5,4,5这4个节点,即a[5],a[9],a[10],a[11];操作两次更新两次

但是lazy就不会,直接在这个阶段自增两次,等到下次要操作其子区间如[4,5]时,才会把lazy标记往下传递并且更新数值


下面上两个代码:一个超时(每次都下放子区间),一个是AC的lazy标记的

仔细比较比较就会有很大的区别(虽然代码就一两句话,但是原理完全不同)


int n,m,t,ans;
int tree[maxn];
int ansnum[maxn];

struct node{
	int l,r;
}a[maxn];

void add(int L,int R,int l,int r,int rt){
	if (l>=L&&r<=R) tree[rt]++;
	if (tree[rt]>=2) return;
	if (l==r) return;
	int mid=(l+r)>>1;
	add(L,R,l,mid,rt<<1);
	add(L,R,mid+1,r,rt<<1|1);
	if (tree[rt<<1]>=2&&tree[rt<<1|1]>=2) tree[rt]=2;
	return;
}

bool query(int L,int R,int l,int r,int rt){
	if (tree[rt]>=2) return true;
	if (l>=L&&r<=R)
		if (tree[rt]<2) return false;
		else return true;
	int mid=(l+r)>>1;
	if (R<=mid) return query(L,R,l,mid,rt<<1);
	else if (L>mid) return query(L,R,mid+1,r,rt<<1|1);
	else return query(L,R,l,mid,rt<<1)&&query(L,R,mid+1,r,rt<<1|1);
}

int main(){
	//input;
	scanf("%d",&t);
	while(t--){
		memset(tree,0,sizeof(tree));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a[i].l,&a[i].r);
			add(a[i].l,a[i].r,1,n,1);
		}
		ans=0;
		for(int i=1;i<=m;i++)
			if (query(a[i].l,a[i].r,1,n,1)){
				ans++;
				ansnum[ans]=i;
			}
		printf("%d\n",ans);
		for(int i=1;i<=ans;i++)
			printf("%d%c",ansnum[i],i==ans?'\n':' ');
	}
	return 0;
}

int n,m,t,ans;
int add[maxn<<2];
int sum[maxn<<2];
int ansnum[maxn<<2];

struct node{
	int l,r;
}a[maxn];

void PushUp(int rt){
	if (sum[rt<<1]>=2&&sum[rt<<1|1]>=2) sum[rt]=2;
}

void PushDown(int rt){
	if (add[rt]){
		add[rt<<1]+=add[rt];
		add[rt<<1|1]+=add[rt];
		sum[rt<<1]+=add[rt];
		sum[rt<<1|1]+=add[rt];
		add[rt]=0;
	}
}

void update(int L,int R,int l,int r,int rt){
	if (l>=L&&r<=R){
		add[rt]++;
		sum[rt]++;
		return;
	}
	PushDown(rt);
	int mid=(l+r)>>1;
	if (L<=mid) update(L,R,lson);
	if (R>mid) update(L,R,rson);
	PushUp(rt);
}

bool query(int L,int R,int l,int r,int rt){
	if (l>=L&&r<=R){
		if (sum[rt]>=2) return true;
		else return false;
	}
	PushDown(rt);
	int mid=(l+r)>>1;
	bool ans;
	if (R<=mid) ans=query(L,R,lson);
	else if (L>mid) ans=query(L,R,rson);
	else ans=query(L,R,lson)&&query(L,R,rson);
	PushUp(rt);
	return ans;
}

int main(){
	//input;
	scanf("%d",&t);
	while(t--){
		memset(add,0,sizeof(add));
		memset(sum,0,sizeof(sum));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a[i].l,&a[i].r);
			update(a[i].l,a[i].r,1,n,1);
		}
		ans=0;
		for(int i=1;i<=m;i++)
			if (query(a[i].l,a[i].r,1,n,1)){
				ans++;
				ansnum[ans]=i;
			}
		printf("%d\n",ans);
		for(int i=1;i<=ans;i++)
			printf("%d%c",ansnum[i],i==ans?'\n':' ');
	}
	return 0;
}

PS1:这个题用暴力做的话(直接for循环判断),必须超时不然没天理

PS2:这个题可以用RMQ(查询区间最小值的最优算法):常数级,弱暂时还不会

PS3:推荐个学习线段树的PDF:

ACM大牛总结的线段树专辑,超经典的

搞大一点显得很霸气


PS4:这个题是抢钱的分水岭,如果前几天会的话,说不定就有奖金了哎,知识就是命运啊(money)啊