asp网站跳转浏览器,28创业商机网,网站建设无法访问网站,系部网站建设方案正题
题目链接:https://cometoj.com/contest/79/problem/E?problem_id4207 题目大意 nnn个栈#xff0c;要求支持操作 l∼rl\sim rl∼r区间内的栈压入一个数l∼rl\sim rl∼r区间内的栈弹出一个数求第xxx个栈内第kkk个数 解题思路
对于每个询问我们其实就是要求在他之前的第…正题
题目链接:https://cometoj.com/contest/79/problem/E?problem_id4207 题目大意
nnn个栈要求支持操作
l∼rl\sim rl∼r区间内的栈压入一个数l∼rl\sim rl∼r区间内的栈弹出一个数求第xxx个栈内第kkk个数 解题思路
对于每个询问我们其实就是要求在他之前的第一个位置使得栈内有t−kt-kt−k个数的操作。
我们可以倒着跑维护一个线段树表示每个询问的“倒计时”如果是压入就对于所有询问−1-1−1弹出就是111然后每次操作后0的询问答案就是该次操作。
这里可以先把没有接触到的询问都赋值为infinfinf触碰到后再修改“倒计时”
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define lowbit(x) (x-x)
using namespace std;
const ll N2e510,inf1e9;
ll n,q,l[N],r[N],v[N];
ll cnt,p[N],L[N],R[N],ans[N];
ll w[N*4],num[N*4],lazy[N*4];
void Merge(ll x){w[x]min(w[x*2],w[x*21]);if(w[x*2]w[x*21])num[x]num[x*2];else num[x]num[x*21];return;
}
void Downdata(ll x){if(!lazy[x])return;w[x*2]lazy[x];w[x*21]lazy[x];lazy[x*2]lazy[x];lazy[x*21]lazy[x];lazy[x]0;return;
}
void Build(ll x,ll l,ll r){if(lr){w[x]inf;num[x]l;return;}ll mid(lr)1;Build(x*2,l,mid);Build(x*21,mid1,r);Merge(x);return;
}
void Updata(ll x,ll L,ll R,ll pos,ll val){if(LR)w[x]val;if(LR)return;ll mid(LR)1;Downdata(x);if(posmid)Updata(x*2,L,mid,pos,val);else if(posmid)Updata(x*21,mid1,R,pos,val);Merge(x);return;
}
void Add(ll x,ll L,ll R,ll l,ll r,ll val){if(LR||lr)return;if(L1||Rcnt)return;if(lLRr){w[x]val;lazy[x]val;return;}ll mid(LR)1;Downdata(x);if(rmid)Add(x*2,L,mid,l,r,val);else if(lmid)Add(x*21,mid1,R,l,r,val);else Add(x*2,L,mid,l,r,val),Add(x*21,mid1,R,l,r,val);Merge(x);return;
}
bool cmp(ll x,ll y)
{return (l[x]l[y])?(xy):(l[x]l[y]);}
int main()
{scanf(%lld%lld,n,q);for(ll i1;iq;i){char op[10];scanf(%s,op);if(op[1]u){scanf(%lld%lld%lld,l[i],r[i],v[i]);}if(op[1]o){scanf(%lld%lld,l[i],r[i]);v[i]-inf;}if(op[1]i){scanf(%lld%lld,l[i],r[i]);p[cnt]i;}}sort(p1,p1cnt,cmp);for(ll i0;in1;i)L[i]cnt1;for(ll i1;icnt;i){v[p[i]]-i;L[l[p[i]]]min(L[l[p[i]]],i);R[l[p[i]]]max(R[l[p[i]]],i);}for(ll in-1;i1;i--)L[i]min(L[i],L[i1]);for(ll i2;in;i)R[i]max(R[i],R[i-1]);if(!cnt)return 0;Build(1,1,cnt);for(ll iq;i1;i--){if(v[i]0){Add(1,1,cnt,L[l[i]],R[r[i]],-1);while(w[1]0){ans[p[num[1]]]v[i];Updata(1,1,cnt,num[1],inf);}}else if(v[i]-cnt)Add(1,1,cnt,L[l[i]],R[r[i]],1);else{Updata(1,1,cnt,-v[i],r[i]);}}for(ll i1;iq;i)if(v[i]-cntv[i]0)printf(%lld\n,ans[i]);return 0;
}
