洛谷 P1533 可怜的狗狗

Description

• 小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

  可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。

Input

• 第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；m表示他喂了m次。

  第二行n个整数，表示第i只狗的漂亮值为ai。

  接下来m行，每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。

Output

• M行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

Sample Input

7 2
1 5 2 6 3 7 4
1 5 3
2 7 1

Sample Output

3

2

题解：

• 平衡树。
• 首先一说这题解法很多，莫队、主席树、划分树、线段树、平衡树。
• 这题用平衡树还是比较巧妙的。观察到题目中有这么一个性质：每个区间（i,j）不互相包含。这就说明，原本下列的3种情况：（/为占位符）

//第一种

………..

///////…………

//第二种

………..

///……

//第三种

………..

////////////////// ………

• 只会变成下列两种

//第一种

………..

///////…………

//第二种

………..

///////////////////// ………

• 那么先离线把区间保存下来，按左端点从小到大排序。如果与上一个区间有重叠部分：就删掉上一个区间中与当前区间不重叠的部分，再加上当前新的部分。如果与上一个区间没有重叠部分，就删掉上一个区间，添加当前区间。这样操作就可以得到当前区间。
• 有了这样的性质，每个位置的元素至多被删除/添加一次，复杂度就是O(nlogn)，完全可以接受。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 300005
#define M 50005
#define inf 0x7fffffff
using namespace std;

struct T {int l, r, val, dat, cnt, size;} t[N];
struct B {int l, r, k, id;} b[M];
int n, m, root, tot;
int a[N], ans[M];

int read()
{
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return x *= f;
}

bool cmp(B x, B y)
{
    if(x.l == y.l) return x.r < y.r;
    return x.l < y.l;
}

void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;}

int New(int val)
{
    t[++tot].val = val, t[tot].dat = rand();
    t[tot].size = t[tot].cnt = 1;
    return tot;
}

void zig(int &y)
{
    int x = t[y].l;
    t[y].l = t[x].r, t[x].r = y, y = x;
    up(t[y].r), up(y);
}

void zag(int &x)
{
    int y = t[x].r;
    t[x].r = t[y].l, t[y].l = x, x = y;
    up(t[x].l), up(x);
}

void insert(int &p, int val)
{
    if(!p) {p = New(val); return;}
    if(val == t[p].val) {t[p].cnt++, up(p); return;}
    if(val < t[p].val)
    {
        insert(t[p].l, val);
        if(t[t[p].l].dat > t[p].dat) zig(p);
    }
    else
    {
        insert(t[p].r, val);
        if(t[t[p].r].dat > t[p].dat) zag(p);
    }
    up(p);
}

void erase(int &p, int val)
{
    if(!p) return;
    if(val == t[p].val)
    {
        if(t[p].cnt > 1) {t[p].cnt--, up(p); return;}
        if(t[p].l || t[p].r)
        {
            if(!t[p].r || t[t[p].l].dat > t[t[p].r].dat) zig(p), erase(t[p].r, val);
            else zag(p), erase(t[p].l, val);
            up(p);
        }
        else p = 0;
        return;
    }
    val < t[p].val ? erase(t[p].l, val) : erase(t[p].r, val);
    up(p);
}

int valOfRank(int p, int rank)
{
    if(!p) return inf;
    if(t[t[p].l].size >= rank) return valOfRank(t[p].l, rank);
    if(t[t[p].l].size + t[p].cnt >= rank) return t[p].val;
    return valOfRank(t[p].r, rank - t[t[p].l].size - t[p].cnt);
}

int main()
{
    New(inf), New(-inf), root = 1, t[1].l = 2, up(1);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= m; i++)
    {
        b[i].l = read(), b[i].r = read();
        b[i].k = read(), b[i].id = i;
    }
    sort(b + 1, b + 1 + m, cmp);
    for(int i = 1; i <= m; i++)
    {
        if(b[i - 1].r >= b[i].l)
        {
            for(int j = b[i - 1].l; j < b[i].l; j++) erase(root, a[j]);
            for(int j = b[i - 1].r + 1; j <= b[i].r; j++) insert(root, a[j]);
        }
        else
        {
            for(int j = b[i - 1].l; j <= b[i - 1].r; j++) erase(root, a[j]);
            for(int j = b[i].l; j <= b[i].r; j++) insert(root, a[j]);
        }
        ans[b[i].id] = valOfRank(root, b[i].k + 1);
    }
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}