51nod 2014 小朋友的笑话（势能分析线段树）

灰太狼 2021-12-05 20:35 220阅读 0赞

## 题意： ##

小O是一个很萌很萌的女孩子。  
有一天小O叫了很多很多萌萌哒小朋友到家里来玩。  
由于太无聊了，她们开始讲笑话。  
总共有N个小朋友排成一排，编号1~N。  
在某个时刻，会有编号为xi的小朋友看到了笑话li，然后她会把这个笑话讲出来，与她距离不超过ki的小朋友都会听到这个笑话。  
当一个小朋友听到一个笑话时，如果她是第一次听得到这个笑话，那么她会觉得这个笑话非常好笑，笑的停不下来。如果她听到之前就是在笑的她会继续笑。  
如果她之前听过这个笑话，那么她会觉得这个笑话非常无聊，她会立即停止笑。  
  
现在小O想知道，在某些时刻一段区间内有多少小朋友在笑。

收起

# 输入 #

第一行两个整数N,M，表示小朋友的数量和事件数量，(1<=N,M<=100000)
    接下来M行
    第一行为一个正整数op（1<=op<=2），表示事件类型。
    如果op=1，接下来三个整数xi li ki，表示该时间点小朋友xi(1<=xi<=N)讲了一个笑话li(1<=li<=100000)，传播距离为ki(0<=ki<=N)。
    如果op=2，接下来两个整数l r，表示该时间点小O想知道区间[l,r]中有多少小朋友在笑(1<=l<=r<=N)

# 输出 #

对每个询问操作，输出答案

# 输入样例 #

10 14
    1 3 11 0
    2 3 3
    1 3 11 2
    2 1 5
    1 5 12 1
    2 4 6
    1 8 13 2
    2 6 10
    1 7 11 2
    2 5 9
    1 10 12 1
    2 9 11
    1 9 12 0
    2 1 10

# 输出样例 #

1
    4
    3
    5
    4
    2
    7

## 分析：我们用一个线段树来维护每个小朋友当前的状态（笑还是不笑）。然后对每个笑话种类使用一个set来维护目前为止听过该笑话的小朋友的区间的集合，要求set里记录的区间是没有交的。对于听到了一个笑话，我们在该笑话种类的set里插入该区间；该区间会被原有区间分成若干份，将与原有区间有交的那部分在线段树里设为不笑，与原有区间无交的那部分在线段树里设为笑。最后将set里的区间合并（若干个有交的区间合并成一个大区间），保持set中区间无交的性质。复杂度是O(MlogN)。 ##

## 参考：[http://www.51nod.com/Challenge/ProblemSolution.html\#problemId=2014][http_www.51nod.com_Challenge_ProblemSolution.html_problemId_2014]、[https://blog.csdn.net/qq\_35950004/article/details/88780448][https_blog.csdn.net_qq_35950004_article_details_88780448]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define lc now<<1
    #define rc now<<1|1
    const int N = 1e5+5;
    int n,m;
    struct node{
    	int l,r,col;
    	node(int l=0,int r=0,int col=0):l(l),r(r),col(col){}
    	bool operator <(const node &B)const{ return l < B.l; }
    };
    set<node >st[N];
    set<node >::iterator it,it2;
    
    int sum[N<<3],tag[N<<3],siz[N<<3];
    
    void Build(int now,int l,int r){
    	siz[now] = r - l + 1;
    	tag[now] = -1;
    	if(l == r) return;
    	int mid = (l+r) >> 1;
    	Build(lc,l,mid) , Build(rc,mid+1,r);
    }
    
    void dt(int now){
    	if(tag[now] == 0){
    		sum[now] = 0;
    		tag[lc] = tag[rc] = 0;
    	}
    	if(tag[now] == 1){
    		sum[now] = siz[now];
    		tag[lc] = tag[rc] = 1;
    	}
    	tag[now] = -1;
    }
    
    void upd(int now){
    	sum[now] = sum[lc] + sum[rc];
    }
    
    void Insert(int now,int l,int r,int ql,int qr,int col){
    	dt(now);
    	if(l > qr || ql > r) return;
    	if(ql<=l && r<=qr){
    		tag[now] = col;
    		dt(now);
    		return;
    	}
    	int mid = (l+r) >> 1;
    	Insert(lc,l,mid,ql,qr,col);
    	Insert(rc,mid+1,r,ql,qr,col);
    	upd(now);
    }
    
    int Query(int now,int l,int r,int ql,int qr){
    	dt(now);
    	if(l > qr || ql > r) return 0;
    	if(ql<=l && r<=qr) return sum[now];
    	int mid = (l+r) >> 1;
    	int ret = Query(lc,l,mid,ql,qr) + Query(rc,mid+1,r,ql,qr);
    	upd(now);
    	return ret;
    }
    
    int main(){
    	scanf("%d%d",&n,&m);
    	Build(1,1,n);
    	for(int i=1;i<=100000;i++) st[i].insert(node(1,n,0));
    	for(int i=1,op,l,r,x,k;i<=m;i++){
    		scanf("%d",&op);
    		if(op == 1){
    			scanf("%d%d%d",&x,&l,&k);
    			x-=k,k=2*k+x;
    			x = max(x , 1) , k = min(k , n);
    			it = st[l].upper_bound(x);
    			it--;
    			int mn = x , mx = k;
    			for(;it!=st[l].end() && (*it).l<=k;){
    				Insert(1,1,n,max((*it).l,x),min((*it).r,k),(*it).col!=1);
    				if((*it).col == 1)
    					mn = min(mn , (*it).l),
    					mx = max(mx , (*it).r);
    				it2 = it , it++;
    				int L = (*it2).l , R = (*it2).r , C = (*it2).col;
    				st[l].erase(it2);
    				if(C == 0 && L < x)
    					st[l].insert(node(L,x-1,0));
    				if(C == 0 && R > k)
    					st[l].insert(node(k+1,R,0));
    			}
    			st[l].insert(node(mn,mx,1));
    		}
    		else{
    			scanf("%d%d",&l,&r);
    			printf("%d\n",Query(1,1,n,l,r));
    		}
    	}
    	return 0;
    }

[http_www.51nod.com_Challenge_ProblemSolution.html_problemId_2014]: http://www.51nod.com/Challenge/ProblemSolution.html#problemId=2014
[https_blog.csdn.net_qq_35950004_article_details_88780448]: https://blog.csdn.net/qq_35950004/article/details/88780448