[HEOI2016/TJOI2016]排序

嘟嘟嘟

首先这题的暴力是十分好写的，而且据说能得不少分。

正解写起来不难，就是不太好想。

根据做题经验，我想到了给这个序列转化成01序列，但是接下来我就不会了。还是看了题解。

因为查询只有一个数，所以可以二分答案：把大于等于mid的数标记成1，小于mid的数为0.这样排序就是区间赋值了，线段树可做。

那怎么检验mid是否正确呢？其实这个是有单调性的：如果二分的是1，那么很显然最后位置\(q\)上一定是1，随着二分的值变大，位置\(q\)上是1的可能性就越小。这大抵就是二分的单调性？

（这只能算是感性理解吧）

或者说如果第\(Q\)位是1，那么答案就是\([mid, R]\)，否则就是\([L, mid - 1]\)。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 1e5 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, m, Q, a[maxn];

bool b[maxn];

struct Node

{

  int op, L, R;

}q[maxn];

int l[maxn << 2], r[maxn << 2], sum[maxn << 2], lzy[maxn << 2];

In void build(int L, int R, int now)

{

  l[now] = L, r[now] = R;

  lzy[now] = -1;

  if(L == R) {sum[now] = b[L]; return;}

  int mid = (L + R) >> 1;

  build(L, mid, now << 1);

  build(mid + 1, R, now << 1 | 1);

  sum[now] = sum[now << 1] + sum[now << 1 | 1];

}

In void change(int now, int flg)

{

  sum[now] = (r[now] - l[now] + 1) * flg;

  lzy[now] = flg;

}

In void pushdown(int now)

{

  if(~lzy[now])

    {

      change(now << 1, lzy[now]), change(now << 1 | 1, lzy[now]);

      lzy[now] = -1;

    }

}

In void update(int L, int R, int now, int flg)

{

  if(L > R) return;

  if(l[now] == L && r[now] == R) {change(now, flg); return;}

  pushdown(now);

  int mid = (l[now] + r[now]) >> 1;

  if(R <= mid) update(L, R, now << 1, flg);

  else if(L > mid) update(L, R, now << 1 | 1, flg);

  else update(L, mid, now << 1, flg), update(mid + 1, R, now << 1 | 1, flg);

  sum[now] = sum[now << 1] + sum[now << 1 | 1];

}

In int query(int L, int R, int now)

{

  if(l[now] == L && r[now] == R) return sum[now];

  pushdown(now);

  int mid = (l[now] + r[now]) >> 1;

  if(R <= mid) return query(L, R, now << 1);

  else if(L > mid) return query(L, R, now << 1 | 1);

  else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1);

}

In bool judge(int x)

{

  for(int i = 1; i <= n; ++i) b[i] = (a[i] >= x);

  build(1, n, 1);

  for(int i = 1; i <= m; ++i)

    {

      int tp = query(q[i].L, q[i].R, 1);

      if(!q[i].op)

	{

	  update(q[i].L, q[i].R - tp, 1, 0);

	  update(q[i].R - tp + 1, q[i].R, 1, 1);

	}

      else

	{

	  update(q[i].L, q[i].L + tp - 1, 1, 1);

	  update(q[i].L + tp, q[i].R, 1, 0);

	}

    }

  return query(Q, Q, 1);

}

int main()

{

  n = read(), m = read();

  for(int i = 1; i <= n; ++i) a[i] = read();

  for(int i = 1; i <= m; ++i) q[i].op = read(), q[i].L = read(), q[i].R = read();

  Q = read();

  int L = 1, R = n;

  while(L < R)

    {

      int mid = (L + R + 1) >> 1;

      if(judge(mid)) L = mid;

      else R = mid - 1;

    }

  write(L), enter;

  return 0;

}

巴特西

[HEOI2016/TJOI2016]排序

最新文章

热门文章