P3901

题意

有一个长度为

n

的序列

a

，

q

次询问，问

[l,r]

中是不是互不相同。

题解

题解区里一车子莫队，但我不会莫队，用一个非常神秘的算法交一发过了，故写题解。

令

lst_{i}

为

a

中与其相同的上一个数的位置，如果一个区间不合法，他肯定同时包含

lst_{i}

和

i

。

然后就可以把所有区间拉出来，按照左端点排序并离线处理。

让

i

在

1 \sim n

从小到大枚举，如果遇到左端点就把这个区间加入到一个容器里，遇到右端点就把这个区间从容器里退出。

重头戏来了：每遇到一个

i

，就把看容器里的区间有几个其左节点在

lst_{i}

前，那么这些区间里肯定都不互不相同，答案就是 No。

跑完一遍没有跑出来上面这个情况的，答案就是 Yes。

至于这个容器……可以用 set 啊，又满足加入，还满足删除，甚至可以按照左端点把加入的节点排序！

加个具体实现：

枚举

i \in [1,n]

，遇到一个左端点为

i

，将其加入 set 里。

然后对于

i

，枚举左端点在

lst_{i}

前的所有区间将其退掉，然后让其答案为 No，借助 set 强大的排序功能，可以很轻松的找这些。

最后退掉右端点在

i

的，用一个堆将所有在 set 里的按右端点从小到大排序，那么如果存在，右端点在

i

的一定在堆顶（右端点小于

i

的已经被退了），接着就把这些在 set 里使用 find() 函数找一下，找到就退，找不到（可能之前答案已经设定了）就不用退了。

~~STL 很好玩吧！~~

然后就做完了，复杂度

O(n \log q)

。

代码

CPP

#include<bits/stdc++.h>
#define pii pair<int,int>
#define si set<pair<int,int> >::iterator
using namespace std;
const int N=1e5+5;
int n,q;
int a[N],lst[N],lsta[N],reff[N];
struct query {
	int l,r,id;
	bool ans;
} s[N];
bool cmp(query a,query b) {
	return a.l<b.l;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		lst[i]=lsta[a[i]];
		lsta[a[i]]=i;
	}
	for(int i=1;i<=q;i++) cin>>s[i].l>>s[i].r,s[i].id=i;
	sort(s+1,s+1+q,cmp);
	for(int i=1;i<=q;i++) reff[s[i].id]=i;
	set<pii> S;
	priority_queue<pii> del;
	int x=1;
	for(int i=1;i<=n;i++) {
		while(i==s[x].l) S.insert({s[x].l,x}),del.push({-s[x].r,x}),x++;
		//加入左端点在 i 的区间 
		for(si j=S.begin(),ERASE;(*j).first<=lst[i]&&j!=S.end();) { //左端点在 lst[i] 及以前的答案都是 No
			s[(*j).second].ans=1;
			ERASE=j,j++;
			S.erase(ERASE); //删掉，让每个区间至多被判一次，这样复杂度正确的
		}
		while(del.size()&&-del.top().first==i) {
			int xx=del.top().second;
			del.pop();
			si FIND=S.find({s[xx].l,xx});
			if(FIND!=S.end()) S.erase(FIND);
		} //堆会按照第一关键字排序，可以轻松把右端点在 i 的退掉 
	}
	for(int i=1;i<=q;i++) {
		if(s[reff[i]].ans) puts("No");
		else puts("Yes");
	}
	return 0;
}

文章操作

题意

题解

代码

相关推荐

评论

P3901