线段树维护最后一个0的位置(Restore Permutation)Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

摘要:
想法:首先,我们应该认为最后0的位置必须是尚未确定的数字的最小值,所以从1、2、3……继续。如果选中,它将在线段树上更改为INF,上推保持的最右侧位置为0。一开始,我只换了一次衣服就忘了下来。经过长时间的改变,我学会了。

题意:https://codeforc.es/contest/1208/problem/D

给你长度为n的序列,s[i]的值为p[1]到p[i-1]中比p[i]小的数的和,让你求出p序列。

思路:

首先我们要想到,最后一个0的位置一定就是当前剩余还没用确定的数里的最小值,所以从1,2,3 。。。一直下去就行了。

选过了就在线段树上改为INF,同时pushup维护的最右边为0的位置。

一开始单点修改忘记down下去了,改了好久,学到了学到了。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 const double E=2.718281828;
 46 const double PI=acos(-1.0);
 47 const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const double ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 const int N=(int)2e5+10;
 52 
 53 ll a[N];
 54 ll add[N<<2],min_[N<<2];
 55 int POS[N<<2];
 56 
 57 void up(int rt,int l,int r)
 58 {
 59     min_[rt]=min(min_[rt<<1],min_[rt<<1|1]);
 60     if(min_[ls]<min_[rs]) POS[rt]=POS[ls];
 61     else POS[rt]=POS[rs];
 62 }
 63 
 64 void dn(int rt)
 65 {
 66     if(add[rt]!=0)
 67     {
 68         add[ls]+=add[rt];
 69         add[rs]+=add[rt];
 70         min_[rt<<1]+=add[rt];
 71         min_[rt<<1|1]+=add[rt];
 72         add[rt]=0;
 73     }
 74 }
 75 
 76 void Build(int l,int r,int rt)
 77 {
 78     if(l==r)
 79     {
 80         min_[rt]=a[l];
 81         POS[rt]=l;
 82         add[rt]=0;
 83         return;
 84     }
 85     int mid=(l+r)>>1;
 86 
 87     Build(l,mid,rt<<1);
 88     Build(mid+1,r,rt<<1|1);
 89     up(rt,l,r);
 90 }
 91 
 92 void update_dot(int pos,ll V,int l,int r,int rt)
 93 {
 94     if(l==r)
 95     {
 96         min_[rt]=V;
 97         return;
 98     }
 99 
100     int mid=(l+r)>>1;
101     dn(rt);
102     if(pos<=mid)
103         update_dot(pos,V,l,mid,rt<<1);
104     else
105         update_dot(pos,V,mid+1,r,rt<<1|1);
106     up(rt,l,r);
107 }
108 void update_qu(int L,int R,int V,int l,int r,int rt)
109 {
110     if(L>R)return;
111     if(L<=l&&r<=R)
112     {
113         min_[rt]+=V;
114         add[rt]+=V;
115         return;
116     }
117 
118     int mid=(l+r)>>1;
119     dn(rt);
120     if(L<=mid)
121         update_qu(L,R,V,l,mid,rt<<1);
122     if(R>mid)
123         update_qu(L,R,V,mid+1,r,rt<<1|1);
124     up(rt,l,r);
125 }
126 void check(int pos,int l,int r,int rt)
127 {
128     if(l==r)
129     {
130         cout<<min_[rt]<<' ';
131         return ;
132     }
133     int mid=(l+r)>>1;
134 
135     dn(rt);
136     if(pos<=mid)
137         check(pos,l,mid,rt<<1);
138     else
139         check(pos,mid+1,r,rt<<1|1);
140 }
141 int ans[N];
142 int main()
143 {
144 //    fill(min_,min_+N-3,INF);
145     int n;
146     sc("%d",&n);
147     for(int i=1;i<=n;++i)
148         sc("%lld",&a[i]);
149     Build(1,n,1);
150     for(int i=1;i<=n;++i)
151     {
152         int p=POS[1];
153     //    pr("%d: %d
",i,p);
154         ans[p]=i;
155         update_dot(p,INF,1,n,1);
156     //    for(int j=1;j<=n;++j)check(j,1,n,1);cout<<endl;
157         update_qu(p+1,n,-i,1,n,1);
158     //    for(int j=1;j<=n;++j)check(j,1,n,1);cout<<endl;
159     }
160     for(int i=1;i<=n;++i)
161         pr("%d ",ans[i]);
162     return 0;
163 }
164 
165 /**************************************************************************************/
166 
167 int maxx(int a,int b)
168 {
169     return a>b?a:b;
170 }
171 
172 void swapp(int &a,int &b)
173 {
174     a^=b^=a^=b;
175 }
176 
177 int lowbit(int n)
178 {
179     return n&(-n);
180 }
181 
182 int Del_bit_1(int n)
183 {
184     return n&(n-1);
185 }
186 
187 int abss(int a)
188 {
189     return a>0?a:-a;
190 }
191 
192 double fabss(double a)
193 {
194     return a>0?a:-a;
195 }
196 
197 int minn(int a,int b)
198 {
199     return a<b?a:b;
200 }

免责声明:文章转载自《线段树维护最后一个0的位置(Restore Permutation)Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇RMQ+差分处理(Let Them Slide)Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)n*n矩阵 每行每列XOR为0(思维)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

P1558 色板游戏 线段树(区间修改,区间查询)

题意: 给n,m,k,n长度,k个操作,m种颜色 操作C:输入A,B,C,区间【A,B】变成C颜色,可能A>B,所以要确保A<B 操作P:输入A,B,区间【A,B】的颜色种类 思路: 因为颜色只有30种,可以用位运算,然后进行lazy标记 #include<bits/stdc++.h> using namespacestd; #de...

[P6492] [COCI2010-2011#6] STEP(线段树区间合并)

【原题】 题目描述 给定一个长度为 (n) 的字符序列 (a),初始时序列中全部都是字符 L。 有 (q)次修改,每次给定一个 (x),若 (a_x) 为 L,则将 (a_x)修改成 R,否则将 (a_x) 修改成 L。 对于一个只含字符 L,R 的字符串 (s),若其中不存在连续的 L 和 R,则称 (s) 满足要求。 每次修改后,请输出当前序列 (a)...

[P1637] 三元上升子序列 (线段树+离散化)

【原题】 题目描述 Erwin 最近对一种叫 thair 的东西巨感兴趣。。。 在含有 nnn 个整数的序列 (a1,a2,…,an) 中,三个数被称作thair当且仅当 (i<j<k) 且 (ai<aj<ak)。 求一个序列中 thair 的个数。 输入格式 开始一行一个正整数(n), 以后一行 (n) 个整数 (a1,a2,…,a...

hdu 1698 线段树区间更新**懒惰标记

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1698 题意:给n个钩子,每次都会更新从X到Y这个范围的钩子价值,最后求钩子的总价值。初始的钩子价值为1. 直接暴力求解是会超时,需要有线段树懒惰标记维护数据。 线段树的懒惰标记,直接记录了在X到Y之间的数据,这样可以减少递归总数。 1 #include<...

bzoj 4372: 烁烁的游戏 动态点分治+树链剖分+线段树

[Submit][Status][Discuss] Description 背景:烁烁很喜欢爬树,这吓坏了树上的皮皮鼠。 题意: 给定一颗n个节点的树,边权均为1,初始树上没有皮皮鼠。 烁烁他每次会跳到一个节点u,把周围与他距离不超过d的节点各吸引出w只皮皮鼠。皮皮鼠会被烁烁吸引,所以会一直待在节点上不动。 烁烁很好奇,在当前时刻,节点u有多...

未曾设想的道路(线段树)

https://ac.nowcoder.com/acm/contest/11244/C 题解: 考虑只需要区间修改,求历史最大值 那么用线段树的话我们需要维护历史标记最大值,当前标记,区间当前最大值,历史区间最大值 其实现在变成求历史K大可以类似维护 我们维护历史标记最大的K个,当前标记,区间当前最大的K个,区间历史最大的K个 这样子updata的时候是比较...