POJ2104 K-th Number（整体二分）

时间：2023-03-09 18:46:38
POJ2104 K-th Number（整体二分）

嘟嘟嘟



整体二分是一个好东西。

理解起来还行。



首先，需要牢记的是，我们二分的是答案，也就是在值域上二分，同时把操作分到左右区间中（所以操作不是均分的）。

然后我就懒得讲了……

李煜东的《算法竞赛进阶指南》第二版中讲的特别好，有兴趣的OIer可以拿来读读。



这里贴一个板儿。

突然想说一嘴：这道题我们应该保证所有修改（赋值）操作在询问操作之前。虽然代码中没有明显的排序，但是因为读入的时候就先把赋值操作放进操作队列里了，所以二分的每一层，询问区间中一定先是修改，再是询问。

#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 rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const int Max = 1e9;

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, cnt = 0;

struct Node

{

  int x, y, k, id;

}t[maxn << 1], tl[maxn << 1], tr[maxn << 1];

int ans[maxn];

int c[maxn];

int lowbit(int x) {return x & -x;}

void clear(int pos)

{

  for(; pos <= n; pos += lowbit(pos))

    if(c[pos]) c[pos] = 0;

    else return;

}

void update(int pos, int d)

{

  for(; pos <= n; pos += lowbit(pos)) c[pos] += d;

}

int query(int pos)

{

  int ret = 0;

  for(; pos; pos -= lowbit(pos)) ret += c[pos];

  return ret;

}

void solve(int l, int r, int ql, int qr)

{

  if(ql > qr) return;

  if(l == r)

    {

      for(int i = ql; i <= qr; ++i)

	if(t[i].id) ans[t[i].id] = l;

      return;

    }

  int mid = (l + r) >> 1;

  int id1 = 0, id2 = 0;

  for(int i = ql; i <= qr; ++i)

    {

      if(!t[i].id)

	{

	  if(t[i].k <= mid) update(t[i].x, 1), tl[++id1] = t[i];

	  else tr[++id2] = t[i];

	}

      else

	{

	  int sum = query(t[i].y) - query(t[i].x - 1);

	  if(sum >= t[i].k) tl[++id1] = t[i];

	  else t[i].k -= sum, tr[++id2] = t[i];

	}

    }

  for(int i = ql; i <= qr; ++i) if(!t[i].id && t[i].k <= mid) clear(t[i].x);

  for(int i = 1; i <= id1; ++i) t[ql + i - 1] = tl[i];

  for(int i = 1; i <= id2; ++i) t[ql + id1 + i - 1] = tr[i];

  solve(l, mid, ql, ql + id1 - 1);

  solve(mid + 1, r, ql + id1, qr);

}

int main()

{

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

  for(int i = 1; i <= n; ++i) t[++cnt].x = i, t[cnt].k = read(), t[cnt].id = 0;

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

      t[++cnt].x = read(), t[cnt].y = read(), t[cnt].k = read(), t[cnt].id = i;

  solve(-Max, Max, 1, cnt);

  for(int i = 1; i <= m; ++i) write(ans[i]), enter;

  return 0;

}

相关文章