bzoj 3333: 排队计划 题解

【原题】

3333: 排队计划

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 161  Solved: 71

[Submit][Status]

Description

Input

Output

Sample Input

6 2

160 163 164 161 167 160

2

3

Sample Output

6

3

1

HINT

Source

wyx528命题

【分析】简述一下题目。N个数排成一列,每次指定一个位置P,然后把P~N中所有身高小于等于P的人都拎出来,排一遍序后再放进去。每次操作需要求一遍逆序对。

首先很容易想到:每次选定一个位置P后,减少的逆序对数量就是P~N中满足要求的人原来构成的逆序对——而且当操作完成之后,这些人将永远不会产生逆序对了。考虑到这样的性质,我们可以维护一个数的F[i],表示从I这个位置开始的逆序对数量。(我们并不关心某个位置某一个时刻的值是多少)然后我们用一个线段树维护i~N中的最小值。每次操作寻找P~N的最小值,如果是满足要求的且位置是X,那么我们就把f[x]置为0,然后可以把x位置的数置为无穷大;之后继续寻找,直到找不到为止。因为每个数只会最多被更新一次,所以效率均摊是NlogN的。

【代码】

#include<cstdio>
#include<algorithm>
#define N 500005
#define INF 1000000005
#define Lo(x) (x&-x)
using namespace std;
typedef long long LL;LL ans=0;
struct Tree{int l,r,min,wh;}a[N*3];
int tree[N];//pos P in array to the tree
int pos[N*4];//pos P int tree to the array
int f[N],data[N],c[N],n,cnt,x,i,opt,P,ord,size,now,L,R;
struct array{int x,id;}uni[N];
inline int cmp(const array &a,const array &b){return a.x<b.x;}
inline int ask(int x){int s=0;for (;x;x-=Lo(x)) s+=c[x];return s;}
inline void add(int x){for (;x<=n;x+=Lo(x)) c[x]++;}
void build(int k,int l,int r)
{
  a[k].l=l;a[k].r=r;
  if (l==r) {a[k].min=data[l];pos[k]=l;tree[l]=k;a[k].wh=k;return;}
  int mid=(l+r)>>1;
  if (l<=mid) build(k<<1,l,mid);
  if (r>mid) build(k<<1|1,mid+1,r);
  if (a[k<<1].min<a[k<<1|1].min) a[k].min=a[k<<1].min,a[k].wh=a[k<<1].wh;
  else a[k].min=a[k<<1|1].min,a[k].wh=a[k<<1|1].wh;
}
int query(int k)
{
  if (L<=a[k].l&&a[k].r<=R) return a[k].wh;
  int mid=(a[k].l+a[k].r)>>1,resl=0,resr=0;
  if (L<=mid) resl=query(k<<1);
  if (R>mid) resr=query(k<<1|1);
  if (!resl) return resr;if (!resr) return resl;
  return (a[resl].min<a[resr].min)?resl:resr;
}
void update(int k)
{
  if (a[k].l==a[k].r) {a[k].min=INF;a[k].wh=k;return;}
  int mid=(a[k].l+a[k].r)>>1;
  if (ord<=mid) update(k<<1);else update(k<<1|1);
  if (a[k<<1].min<a[k<<1|1].min) a[k].min=a[k<<1].min,a[k].wh=a[k<<1].wh;
  else a[k].min=a[k<<1|1].min,a[k].wh=a[k<<1|1].wh;
 }
int main()
{
  read(n);read(opt);//读入优化略去
  for (i=1;i<=n;i++) read(x),uni[i]=(array){x,i};
  sort(uni+1,uni+n+1,cmp);
  for (i=1;i<=n;i++)
    data[uni[i].id]=(uni[i].x==uni[i-1].x)?cnt:++cnt;
  for (i=n;i;i--)
    f[i]=ask(data[i]-1),add(data[i]),ans+=(LL)f[i];
  build(1,1,n);printf("%lld\n",ans);
  while (opt--)
  {
    read(P);now=a[tree[P]].min;
    while (now<INF)
    {
      L=P;R=n;ord=query(1);size=a[ord].min;
      if (size>now) break;ord=pos[ord];
      ans-=(LL)f[ord];f[ord]=0;update(1);
    }
    printf("%lld\n",ans);
  }
  return 0;
} 

bzoj 3333: 排队计划 题解

时间: 07-15

bzoj 3333: 排队计划 题解的相关文章

bzoj 3333: 排队计划 解决问题的方法

[原标题] 3333: 排队计划 Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 161  Solved: 71 [Submit][Status] Description Input Output Sample Input 6 2 160 163 164 161 167 160 2 3 Sample Output 6 3 1 HINT Source wyx528命题 [分析]简述一下题目.N个数排成一列.每次指定一个位置P,然后把P~N中全部身高

矩阵乘法专题1——bzoj 1297 [SCOI2009] 迷路题解

题目链接 题意:给两个长度分别为n和m的序列,现在有两种操作:1.分别选择两个序列的一个非空前缀,切两个前缀的最后一位相同,删除之,得到1分(只累计),消耗e:2.直接删除两个序列,消耗值定于两个序列之前删除的元素个数之和,并且使得得到的分有效(之前没有有效分) 分析: 首先,问题其实就是转化成,进行若干次操作1,然后进行操作2 还要找到一个判别标准,来评判较优的状态(贪心) 每次的消耗值比较大,其实可以计算出最大的删除次数,这个值不是很大 状态表示: 简单的,一个状态可以表示为串A的位置.串B

BZOJ 1~10 精简题解

从这星期起,我开始了怒刷BZOJ的旅程.这几天刷了10道题(由于"档期"的原因,所以有几道题没打完-..捂脸--..) 精简题解: 1000 A+B Problem --.. [BeiJing2006]狼抓兔子 裸的网络流,不过data有点大...... 哈,这图的性质太好了,就是一个平面图额,并且也很容易转化成对偶图,So--spfa怒跑之-- [FJOI2007]轮状病毒 Matrix-tree定理 不过,这道题有个线性递推式:f[n] = 3 * f[n - 1] – f[I -

BZOJ 2595 游览计划(插头DP)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2595 题意:给出一个数字矩阵.求一个连通块包含所有的数字0且连通块内所有数字之和最小. 思路:对于每个格子,是0则必须要选.那么对于不选的格子(i,j)在什么时候可以不选呢?必须同时满足以下两个条件: (1)(i,j)不是0: (2)(i-1,j)不选或者(i-1,j)选了但是轮廓线上还有别的地方与(i-1,j)是一个连通块. int Pre[105][N],op[105][N]; s

bzoj 3198: [Sdoi2013]spring 题解

[原题] 3198: [Sdoi2013]spring Time Limit: 40 Sec  Memory Limit: 256 MB Submit: 253  Solved: 95 Description Input Output Sample Input 3 3 1 2 3 4 5 6 1 2 3 0 0 0 0 0 0 4 5 6 Sample Output 2 HINT [题解]这道题明明是水题,坑了我两天!!!真是伤心.发现哈希都不熟练了. 首先很容易想到是2^6枚举01状态,使得1

bzoj 3246 [Ioi2013] Dreaming 题解

[原题] 3246: [Ioi2013]Dreaming Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 194  Solved: 68 Description Serpent(水蛇)生活的地方有N个水坑,编号为0,...,N - 1,有M条双向小路连接这些水坑.每两个水坑之间至多有一条路径(路径包含一条或多条小路)相互连接,有些水坑之间根本无法互通(即M ≤ N-1 ).Serpent走过每条小路需要一个固定的天数,不同的小路需要的天数可能不同.

BZOJ 4103~4105 THUSC2015 题解

T1:BZOJ 4013 xor 题目大意:给定一个长度为n的数列a和一个长度为m的数列b,给定矩阵A,令Ai,j=ai⊕bj,q次询问某个子矩形里的k大值 n≤1000,m≤3?105,q≤500 刚看到这题的时候我发现我不会,看到数据范围的时候我发现出题人也不会-- 如果n=1,那么我们对这m个数建立可持久化Trie树,每次询问的时候查询异或a1的k大值即可 那么现在n=1000,我们只需要把这2000棵Trie树放在一起跑即可 时间复杂度O(m?32+n?q?32) 二分答案会T掉. #i

值得一做》关于一道DP+SPFA的题 BZOJ1003 (BZOJ第一页计划) (easy+)

这是一道数据范围和评测时间水的可怕的题,只是思路有点难想,BUT假如你的思路清晰,完全了解怎么该做,那就算你写一个反LLL和反SLE都能A,如此水的一道题,你不心动吗? 下面贴出题目 Description 物流公司要把一批货物从码头A运到码头B.由于货物量比较大,需要n天才能运完.货物运输过程中一般要转停好几个码头.物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪.由于各种因素的存在,有的时候某个码头会无法装卸货物.这时候就必须修改运输路线,让货物能够按时到达目的地

【待填坑】bzoj上WC的题解

之前在bzoj上做了几道WC的题目,现在整理一下 bzoj2115 去膜拜莫队的<高斯消元解xor方程组> bzoj2597 LCT维护MST bzoj1758 分数规划+树分治+单调队列 bzoj2595 斯坦纳树,一类用spfa转移的dp,具体可以膜拜<spfa算法的优化及应用>(我是不会插头的蒟蒻) bzoj2597 补集思想之后就变成了显然的平方流 bzoj3052 树上带修改莫队算法(如果一无所知的话,可以按2038 1086 3757 3052的顺序做) bzoj145

bzoj 2141: 排队

就是求个动态区间逆序对??是不是和GTY文艺妹子差不多??哦,不是,,, 这个题的话,可以发现的是,每次交换只会对区间内的数产生影响,所以就是求一下区间内比这个L(区间左端点)大的,小的,(减小,加大)比R(区间右端点)大的,小的,(减大,加小),然后把连个数换一下就就行了..我记得是这样..而且这个sb题也是调了好久... 1 #include<bits/stdc++.h> 2 #define N 100005 3 #define LL long long 4 #define inf 0x3