BSOJ 5185【11.08题目】暴力破解

题意：

签到题

容易发现越是后面的操作就能覆盖掉前面的操作，所以考虑倒序处理

注意到(m)的范围极小

所以我们可以直接(O(nm))的暴力覆盖就行了

并且因为每次覆盖有两种选择(0/1)所以我们最后的这段区间的结果也就有两种情况

由询问倒序排序，然后暴力覆盖的时候判断这个区间会不会更新某个点就行（就是有没有被之前的区间完全覆盖，有就(continue)，没有就(ans<<=1)，至于为什么是(<<=1)上面已经解释了）

然后就是代码了

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=2000005,M=1e5+5;
long long n,m,l[M],r[M],ans=1;
bool a[M];
int main(){
	read(n),read(m);
	for(int i=1;i<=m;i++) read(l[i]),read(r[i]);
	for(int i=m;i>=1;i--){
		bool flag=false;
		for(int j=l[i];j<=r[i];j++){
			if(!a[j]){
				a[j]=true;
				flag=true;
			}
		}
		if(flag) ans<<=1;
	}
	cout<<ans;
	return 0;
}

其实这题可以加强一下(m)...然后就可以快乐的白白让选手们多写个线段树啦~