首页 > 代码库 > Permutacja
Permutacja
题意:
要求动态求问是否有一个 1~n 的排列,使得满足 $p_i \leq a_i$,给定 $a_i$ 初始值,接下来 m次单个位置修改,每次求问是否可以构造出来。
解法:
构造一序列使得 $cnt_i$ 表示 $a$ 序列当前 i 的个数,记 $suffix(i)$ 为此序列的后缀和。
那么可以构造出序列 <-> $ 0 \leq suffix(i) - (n-i+1)$,建权值线段树维护 $suffix(i) - (n-i+1)$ 即可。
#include <bits/stdc++.h> #define l(x) ch[x][0] #define r(x) ch[x][1] #define LL long long const int N = 200010; using namespace std; int totn,n,a[N]; int ch[N<<1][2]; LL minv[N<<1],addv[N<<1]; void update(int x) { minv[x] = min(minv[l(x)], minv[r(x)]); } void push(int x) { if(addv[x]==0) return; addv[l(x)] += addv[x], minv[l(x)] += addv[x]; addv[r(x)] += addv[x], minv[r(x)] += addv[x]; addv[x] = 0; } int build(int l,int r) { int x = ++totn; addv[x] = 0; if(l==r) { l(x) = r(x) = 0; minv[x] = -l; return x; } int mid = (l+r)>>1; l(x) = build(l,mid); r(x) = build(mid+1,r); update(x); return x; } void add(int x,int l,int r,int ql,int qr,LL qv) { push(x); if(ql<=l && r<=qr) { addv[x] = qv; minv[x] += qv; return ; } int mid = (l+r)>>1; if(ql<=mid) add(l(x),l,mid,ql,qr,qv); if(mid<qr) add(r(x),mid+1,r,ql,qr,qv); update(x); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i] = n-a[i]+1; } build(1,n); for(int i=1;i<=n;i++) add(1,1,n,a[i],n,1); int m; scanf("%d",&m); if(minv[1]>=0) puts("TAK"); else puts("NIE"); for(int i=1,x,v;i<=m;i++) { scanf("%d%d",&x,&v); v = n-v+1; add(1,1,n,a[x],n,-1); add(1,1,n,v,n,1); a[x] = v; if(minv[1]>=0) puts("TAK"); else puts("NIE"); } return 0; }
Permutacja
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。