Subtask #1

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

时间复杂度：$O(q)$，空间复杂度：$O(n)$。

Subtask #2

暴力模拟。

时间复杂度：$O(nmq)$，空间复杂度：$O(nm)$。

Subtask #3

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

时间复杂度：$O(nq)$，空间复杂度：$O(n+m)$。

Subtask #4

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

时间复杂度：$O(nm+q\log q)$，空间复杂度：$O(n+m+q)$。

Subtask #5

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

时间复杂度：$O(n^2+mq+q\log n)$，空间复杂度：$O(n^2)$。

Subtask #6

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

时间复杂度：$O(mq\log n^2)$，空间复杂度：$O(n+m)$。

Subtask #7

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

时间复杂度：$O(\max(m,q)\log n+q\log 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;
}