- P201's solution
TJ For 过往与现实之历史
- 2025-9-6 23:24:44 @
Subtask #1
由于 实在太大了,而每次增加的区间最多只会加 个数。所以不管每次查询时问的点在哪,都只需要输出这个点到结尾的距离。
时间复杂度:,空间复杂度:。
Subtask #2
暴力模拟。
时间复杂度:,空间复杂度:。
Subtask #3
由于 太小了,所以询问的长度最长为 。但是要注意会超空间,所以存区间首末点,枚举时判断即可。
时间复杂度:,空间复杂度:。
Subtask #4
注意到题目没有强制在线,可以离线。而且 比较小,但空间也比较小,同样只存区间首末点,离线后用双指针直接反复跳。
时间复杂度:,空间复杂度:。
Subtask #5
由于 不大,此时考虑预处理出所有子区间众数的出现次数,然后二分最大长度,如果超出当前区间,则跳到下一个区间继续二分。
时间复杂度:,空间复杂度:。
Subtask #6
二分的思路 存区间首末点,这时不能 求区间众数的出现次数,但是可以用权值线段树维护,二分时区改区查即可。
时间复杂度:,空间复杂度:。
Subtask #7
同样离线,然后双指针,先收缩 指针到询问点,线段树对应修改,接着线段树上二分 指针的最远距离,线段树对应修改,记录 区间的长度,循环。
时间复杂度:,空间复杂度:。
代码
#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;
}