1913: 一条龙送礼物
Submit Page Summary Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 12 Solved: 7
这天一条龙（出题人dota2游戏名称）的好朋友高素质玩家（某素质玩家dota2游戏名称）天天被朋友黑，一条龙觉得太可怜了，一条龙准备送点礼物给他作为安慰。一条龙现在有一个长度为n的整数序列。 然而他的这个好朋友非常喜欢鸽子，他有想对这个序列进行某种变形操作（第一类操作），给出一些区间[l,r]，要求把区间[l, r]的数字变成飞翔的鸽子的翅膀形状（如下图），进行重新排列。 即是说将数字从大到小依次放在鸽子的左右翅膀上面，然后形成一个新的序列。 不仅如此，由于这个朋友还是一个善变的人，在进行上述操作的过程中也可能进行另外一种操作（第二类操作），给出一个数p，将序列变回p个第一类操作之前的状态。 两种操作总共进行m次后，他只挑走这个序列的第k个数给拿走当作自己的礼物。 一条龙想知道最后被拿走的这个数的值是多少。
第1行：n ，m，k (1<=n,m,k<=5e4) 第2行：n个数，每个数a[i]，表示初始序列 1<=a[i]<=2e5 第3~m+2行： 如果是第一类操作，有三个数：1 L R ，表示对区间[L,R]进行上述操作 否则是第二类操作，有两个数：2 p ，撤销最近的p个第一类操作，如果p比第一类操作数的数量还大，那么将序列恢复成最原始的状态。 上述操作中 1<=L<=R<=n 1<=p<=m
一个数，被拿走的值
HNU
不得不说，湖大出得一手好题，出现了一次两题场……
数学什么的、fwt什么的简直被玩坏……最后发现有些题目还可以水过，对就是这题，湖大大佬O(N^2)水过了……
回过头来看这题，这个思想确实非常的巧妙。题目询问的是在经过一系列操作变化之后，第k个数字是多少，那么我们二分这个第k个数的数值。注意到，如果固定了最后第k个数字，那么其他的数字就能够分为两类，即比它大的和比它小的。当变换到最后，第k位比枚举的数字小，那么说明枚举大了；否则说明枚举小了。也就是说，我们只关心最后第k位的数值与枚举的数字的大小关系，那么我们就可以一开始就忽略掉多余信息，把所有比枚举的数字大的数字都变成1，其余变成0。
可能你还没有反应过来这样子做的好处在哪。但是，你很快就发现，你已经不用排序了，更进一步说，一个区间已经可以被分为三段了。对于一个区间，进行完操作之后，它的前后两部分肯定为1，中间部分为0（根据重排规则大的数字放在两边）。这样的话，我们就可以用线段树解决这个问题，区间赋值，O(logN)的时间复杂度。至于细节方面的话，我们要确定比所枚举的数字大的数字个数才能把区间分段。很显然，维护一个区间和即可，这就是选择0和1而不选择其他数字的原因。有了这些，分成三段，区间赋值即可，最后判断第k位是1还是0。
可以说，思路非常的巧妙，机智的丢掉一些无关的细节，让原本复杂的题目可以得到简化，值得借鉴。具体代码如下（为了强化线段树，我们没有用模板）：
#include<bits/stdc++.h> #define MAXN 100100 using namespace std; struct node { int l,r,sum,lazy; } tree[4*MAXN]; int n,m,k,opcnt,a[MAXN]; int q[MAXN][2]; int L,R,MID; inline void build(int i,int l,int r) { tree[i].l=l; tree[i].r=r; tree[i].sum=0; tree[i].lazy=-1; if (l==r) { tree[i].sum=(a[l]>MID); return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; } inline void push_down(int i) { if (tree[i].lazy==-1) return; int lazy=tree[i].lazy; tree[i].lazy=-1; if (tree[i].l==tree[i].r) return; tree[i<<1].lazy=tree[i<<1|1].lazy=lazy; tree[i<<1].sum=(tree[i<<1].r-tree[i<<1].l+1)*lazy; tree[i<<1|1].sum=(tree[i<<1|1].r-tree[i<<1|1].l+1)*lazy; tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; } inline void update(int i,int l,int r,int x) { if (l>r) return; if (tree[i].l==l && tree[i].r==r) { tree[i].sum=(r-l+1)*x; tree[i].lazy=x;return; } push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if (r<=mid) {update(i<<1,l,r,x); push_down(i<<1|1);} else if (l>mid) {update(i<<1|1,l,r,x); push_down(i<<1);} else { update(i<<1,l,mid,x); update(i<<1|1,mid+1,r,x); } tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; } inline int getsum(int i,int l,int r) { if (l>r) return 0; if (l==tree[i].l && tree[i].r==r) return tree[i].sum; push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if (r<=mid) return getsum(i<<1,l,r); else if (l>mid) return getsum(i<<1|1,l,r); else return getsum(i<<1,l,mid)+getsum(i<<1|1,mid+1,r); } inline void solve(int i,int l,int r) { int sum=getsum(1,l,r); int half1=(sum+1)/2; int half2=sum-half1; update(1,l,l+half1-1,1); update(1,r-half2+1,r,1); update(1,l+half1,r-half2,0); } inline bool check() { build(1,1,n); for(int i=1;i<=opcnt;i++) solve(1,q[i][0],q[i][1]); return getsum(1,k,k)==1; } int main() { while(~scanf("%d%d%d",&n,&m,&k)) { int big=-1e9,sma=1e9; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); big=max(big,a[i]); sma=min(sma,a[i]); } opcnt=0; for(int i=1;i<=m;i++) { int x; scanf("%d",&x); if (x==1) { opcnt++; scanf("%d%d",&q[opcnt][0],&q[opcnt][1]); } else { int y;scanf("%d",&y); opcnt=max(opcnt-y,0); } } L=sma; R=big; while(L<R) { MID=(L+R)>>1; if (check()) L=MID+1; else R=MID-1; } while (!check()) MID--; while (check()) MID++; //个人写二分的保险方法…… printf("%d\n",MID); } return 0; }