松原手机网站开发,广东建设工程造价管理协会网站,重庆网站优化排名软件方案,网络营销案例100例小故事CF1208D Restore Permutation
题意#xff1a;
现在有一个从1到n的一个全排列,但是你不知道这个排列到底是什么,但是你有一个sum[i],其中sum[i]表示∑j1i−1(ajai)?aj:0∑_{j1}^{i−1}(a_ja_i)?a_j:0∑j1i−1(ajai)?aj:0,现在给你sum数组,让你求出这…CF1208D Restore Permutation
题意
现在有一个从1到n的一个全排列,但是你不知道这个排列到底是什么,但是你有一个sum[i],其中sum[i]表示∑j1i−1(ajai)?aj:0∑_{j1}^{i−1}(a_ja_i)?a_j:0∑j1i−1(ajai)?aj:0,现在给你sum数组,让你求出这个排列a
题解
如果sum[i]为0说明在位置i前面的所有数都比他大因为排列a是1到n的全排列也就是说对于数字1来说其sum[i]一定为0且在数字1位置后面的所有数的sum[i]一定不为0,因为有更小的1在前面。也就是说sum中最后一个0的位置就是1的位置找到1之后我们可以将1删除如果1的位置是pos那么pos1到n的所有数都要减1此时数字2的sum就会是下一个最右边的0的位置。也就是说每次找最右边0的位置pos那就是第i个数然后将[pos1,n]区间内所有数减i相当于把第i个数给去掉了 线段树区间修改区间查询即可维护
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn4e59;
#define int long long
int a[maxn];
struct node{int l,r;int minn;int lazy;
}tr[maxn1];
void pushup(int rt){tr[rt].minnmin(tr[rt1].minn,tr[rt1|1].minn);
}
void pushdown(int rt){if(tr[rt].lazy){tr[rt1].minntr[rt].lazy;tr[rt1].lazytr[rt].lazy;tr[rt1|1].minntr[rt].lazy;tr[rt1|1].lazytr[rt].lazy;tr[rt].lazy0;}return ;
}
void build(int rt,int l,int r){tr[rt].ll;tr[rt].rr;if(lr){tr[rt].minna[l];return ;}int midlr1;build(rt1,l,mid);build(rt1|1,mid1,r);pushup(rt);
}
ll query(ll rt,ll l,ll r){if(tr[rt].ltr[rt].r)return tr[rt].l;pushdown(rt);if(tr[rt1|1].minn0)return query(rt1|1,l,r);else if(tr[rt1].minn0)return query(rt1,l,r);
}
void update(int rt,int l,int r,int val){if(tr[rt].lr||tr[rt].rl)return ;if(tr[rt].lltr[rt].rr){tr[rt].minnval;tr[rt].lazyval;return ;}pushdown(rt);update(rt1,l,r,val);update(rt1|1,l,r,val);pushup(rt);
}
int p[maxn];
signed main()
{//rd_test();int n;cinn;for(int i1;in;i)cina[i];build(1,1,n);for(int i1;in;i){int posquery(1,1,n);p[pos]i;
// printf(pos%d\n,pos);update(1,pos,pos,4e109);update(1,pos1,n,-1*i);}for(int i1;in;i){coutp[i] ;}coutendl;return 0;//Time_test();
}
