UOJ637 数据结构 - 扫描线、线段树

题意

给定数列 \(\{a_n\}\)，\(m\) 次询问若将 \(a_{l_i},a_{l_i+1},\dots,a_{r_i}\) 这些数 \(+1\)，全局有多少个不同的数。询问相互独立。

题解

我是傻逼吧？

考虑一个数 \(x(1\le x\le \mathbf{n+1})\) 对哪些答案没有贡献。\(x\) 对 \([l,r]\) 没有贡献，当且仅当：

• \([1,l)\) 和 \((r,n]\) 中都没有 \(x\)；
• \([l,r]\) 中没有 \(x-1\)。

相当于 \(\mathcal{O}(n)\) 次矩形加。扫描线直接做就好了。

如果没过，先把所有数组都开大试试。

代码

#include 
#include 
#include 
#include 
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int N=1e6+5;
int n,m,a[N],ans[N];
struct Fenwick{
	int t[N];
	void Add(int p,int k){for(;p<=n;p+=p&-p) t[p]+=k;}
	int Query(int p){int res=0;for(;p;p-=p&-p) res+=t[p]; return res;}
}bit;
struct Query{int i,l,r;} q[N];
struct Command{int p,l,r,w;} comm[N<<2];
int len=0;
void Update(int _ll,int lr,int rl,int rr){
	if(_ll>lr||rl>rr) return;
	comm[++len]={rl,_ll,lr,1},comm[++len]={rr+1,_ll,lr,-1};
}
vector occ[N];
int main(){
	#ifndef zyz
	ios::sync_with_stdio(false),cin.tie(nullptr);
	#endif
	cin>>n>>m;
	For(i,1,n) cin>>a[i],occ[a[i]].push_back(i);
	For(i,1,m) cin>>q[i].l>>q[i].r,q[i].i=i;
	sort(q+1,q+m+1,[](const Query &q1,const Query &q2){return q1.rr) R=min(R,p-1);
		}
		if(!br) Update(L,l,r,R);
	}
	sort(comm+1,comm+len+1,[](const Command &c1,const Command &c2){return c1.p