Subtask #1

由于 kk 实在太大了,而每次增加的区间最多只会加 nn 个数。所以不管每次查询时问的点在哪,都只需要输出这个点到结尾的距离。

时间复杂度:O(q)O(q),空间复杂度:O(n)O(n)

Subtask #2

暴力模拟。

时间复杂度:O(nmq)O(nmq),空间复杂度:O(nm)O(nm)

Subtask #3

由于 kk 太小了,所以询问的长度最长为 nn。但是要注意会超空间,所以存区间首末点,枚举时判断即可。

时间复杂度:O(nq)O(nq),空间复杂度:O(n+m)O(n+m)

Subtask #4

注意到题目没有强制在线,可以离线。而且 mm 比较小,但空间也比较小,同样只存区间首末点,离线后用双指针直接反复跳。

时间复杂度:O(nm+qlogq)O(nm+q\log q),空间复杂度:O(n+m+q)O(n+m+q)

Subtask #5

由于 nn 不大,此时考虑预处理出所有子区间众数的出现次数,然后二分最大长度,如果超出当前区间,则跳到下一个区间继续二分。

时间复杂度:O(n2+mq+qlogn)O(n^2+mq+q\log n),空间复杂度:O(n2)O(n^2)

Subtask #6

二分的思路 ++ 存区间首末点,这时不能 O(1)O(1) 求区间众数的出现次数,但是可以用权值线段树维护,二分时区改区查即可。

时间复杂度:O(mqlogn2)O(mq\log n^2),空间复杂度:O(n+m)O(n+m)

Subtask #7

同样离线,然后双指针,先收缩 ll 指针到询问点,线段树对应修改,接着线段树上二分 rr 指针的最远距离,线段树对应修改,记录 l,rl,r 区间的长度,循环。

时间复杂度:O(max(m,q)logn+qlogq)O(\max(m,q)\log n+q\log q),空间复杂度:O(n+m+q)O(n+m+q)

代码

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=2e5+1,M=5e5+1; 
int n,k,m,x[N],y[N],tree[N<<2],lazy[N<<2];
struct Q{//询问
	int i,x,id;
	bool operator<(const Q&t)const{
		if(x==t.x)return id<t.id;
		return x<t.x;
	}
}a[M];
struct A{//回答
	int x,id;
	bool operator<(const A&t)const{
		return id<t.id;
	}
}ans[M];
map<int,int>mp;//Hash 找点位置
//权值线段树(最大值)
void pushdown(int k){
	if(!lazy[k])return;
	tree[ls]+=lazy[k],lazy[ls]+=lazy[k];
	tree[rs]+=lazy[k],lazy[rs]+=lazy[k];
	lazy[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y)return tree[k]+=v,lazy[k]+=v,void();
	pushdown(k);
	if(x<=mid)modify(ls,l,mid,x,y,v);
	if(y>mid)modify(rs,mid+1,r,x,y,v);
	tree[k]=max(tree[ls],tree[rs]);
}
int ask(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return tree[k];
	int res=0;pushdown(k);
	if(x<=mid)res=max(res,ask(ls,l,mid,x,y));
	if(y>mid)res=max(res,ask(rs,mid+1,r,x,y));
	return res;
}
int ask(int t,int l,int r,int x){//线段树二分找最长区间
	if(l==r)return l-(tree[t]>=k);
	pushdown(t);
	if(x<=mid){
		int res=ask(t<<1,l,mid,x);
		if(res!=mid)return res;
		if(tree[t<<1|1]<k)return r;
		return ask(t<<1|1,mid+1,r,x);
	}
	else return ask(t<<1|1,mid+1,r,x);
}
bool chk(int l,int x){
	if(l>x)return tree[1]<=k;
	return tree[1]<=k&&ask(1,1,n,l,x)<k;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int q,dis,nr,nxt,lst,l,r,c,i;
	cin>>n>>k>>m>>q;
	nxt=lst=dis=0,l=0,r=1,x[0]=1,y[0]=n;
	for(i=1;i<=n;i++)cin>>c,mp[c]=i;
	for(i=1;i<=m;i++)cin>>x[i]>>y[i];
	for(i=1;i<=q;i++)cin>>a[i].x>>c,a[i].id=mp[c],a[i].i=i;
	sort(a+1,a+q+1);//离线排序
	for(i=1;i<=q&&nxt<=m&&r;i++){
		while(lst<a[i].x){//先收缩 l 指针
			modify(1,1,n,l+1,y[lst],-1);
			dis-=y[lst]-l,l=x[++lst]-1;
		}
		if(l!=a[i].id-1)modify(1,1,n,l+1,a[i].id-1,-1);//特判,防止l指针没收缩但改了线段树
		dis-=a[i].id-l-1,l=a[i].id-1;
		while(nxt<=m){//再拓展 r 指针
			if(chk(r,y[nxt]))modify(1,1,n,r,y[nxt],1),dis+=y[nxt]-r+1,r=x[++nxt];//先把整块区间找完
			else{
				nr=ask(1,1,n,r)+1;//二分找最长
				if(r!=nr)modify(1,1,n,r,nr-1,1);//同上(防止r指针没拓展但改了线段树)
				if(nr==y[nxt]+1)dis+=y[nxt]-r+1,r=x[++nxt];
				else{dis+=nr-r,r=nr;break;}
			}
			//注意一层层二分,一层层改
		}
		ans[i].x=dis,ans[i].id=a[i].i;
	}
	for(;i<=q;i++){//细节:r指针如果找完了,剩下的询问就不要拓展r指针了
		while(lst<a[i].x){
			modify(1,1,n,l+1,y[lst],-1);
			dis-=y[lst]-l,l=x[++lst]-1;
		}
		if(l!=a[i].id-1)modify(1,1,n,l+1,a[i].id-1,-1);
		dis-=a[i].id-l-1,l=a[i].id-1;
		ans[i].x=dis,ans[i].id=a[i].i;
	}
	sort(ans+1,ans+q+1);//按编号排序
	for(i=1;i<=q;i++)cout<<ans[i].x<<'\n';
	return 0;
}