View Code of Problem 1067

#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define INF INT_MAX
int n,m,l_b[N],r_b[N],l_t[N],r_t[N],x[N],o[N];

int tot,v[N*2],l[N*2],r[N*2],d[N*2],heap[N*2];

struct node
{
    int x,y;
    bool operator<(const node&b) const
    {
        return y == b.y ? x < b.x : y < b.y;
    }
}q[N*2];
int cnt,ans;
int fa[N];

int merge(int x,int y)
{
    if(!x)
        return y;
    if(!y)
        return x;
    if(v[x] > v[y])
        swap(x,y);
    r[x] = merge(r[x],y);
    if(d[l[x]] < d[r[x]])
        swap(l[x],r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}

inline int init(int x)
{
    tot++;
    v[tot] = x;
    l[tot] = r[tot] = d[tot] = 0;
    return tot;
}

inline int insert(int x,int y)
{
    return merge(x,init(y));
}

inline int top(int x)
{
    return v[x];
}

inline int pop(int x)
{
    return merge(l[x],r[x]);
}

int getfa(int x)
{
    if(x == fa[x])
        return x;
    fa[x] = getfa(fa[x]);
    return fa[x];
}

void mergeSet(int _x,int _y)
{
    _x = getfa(_x);
    _y = getfa(_y);
    if(_x == _y)
        return;
    fa[_x] = _y;
    if(_x < _y)
    {
        l_b[_y] = l_b[_x];
        r_t[l_t[_x]] = _y;
        l_t[_y] = l_t[_x];
    }
    else
    {
        r_b[_y] = r_b[_x];
        l_t[r_t[_x]] = _y;
        r_t[_y] = r_t[_x];
    }
    heap[_y] = merge(heap[_x],heap[_y]);
    x[_y] += x[_x];
    o[_y] += o[_x];
}

int main()
{
    int t;
    cin >> t;
    for(int ii = 1; ii <= t; ii++)
    {
        ans = cnt = tot = 0;
        cin >> n >> m;
        memset(heap,0,sizeof(heap));
        memset(o,0,sizeof(o));
        memset(x,0,sizeof(x));
        int _x,_y,_z,_h;
        l_b[1] = INF;
        r_b[n] = INF;
        l_t[n] = n-1;
        for(int i = 1 ; i < n; i++)
        {
            scanf("%d",&_x);
            l_b[i+1] = r_b[i] = _x;<span style="white-space:pre">				</span>//合并时需要的信息
            l_t[i] = i - 1;
            r_t[i] = i + 1;
        }
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d",&_x,&_y,&_z);
            if(_z == 0)
            {
                ans++;
                heap[_x] = heap[_x] ? insert(heap[_x],_y) : init(_y);
            }
            else
            {
                cnt++;
                q[cnt].x = _x;
                q[cnt].y = _y + 1;
            }
        }
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        sort(q+1,q+1+cnt);
        for(int i = 1; i <= cnt; i++)
        {
            _h = q[i].y;
            _x = q[i].x;
            _x = getfa(_x);
            while(_h > l_b[_x])
            {
                mergeSet(l_t[_x],_x);
                _x = getfa(_x);
            }
            while(_h > r_b[_x])
            {
                mergeSet(r_t[_x],_x);
                _x = getfa(_x);
            }
            while(heap[_x] && top(heap[_x]) < _h) {   //x，o数组统计无水 有水询问的和
                heap[_x] = pop(heap[_x]);
                x[_x]++;
            }
            o[_x]++;
            if(o[_x] >= x[_x]) {
                ans += (o[_x] - x[_x]);
                o[_x] = x[_x] = 0;
            }
        }
        printf("Case #%d: %d\n",ii,ans);
    }
    return 0;
}
/*
F:\temp\16139742.54759\Main.cc:2:25: error: bits/stdc++.h: No such file or directory
F:\temp\16139742.54759\Main.cc: In function 'int merge(int, int)':
F:\temp\16139742.54759\Main.cc:30: error: 'swap' was not declared in this scope
F:\temp\16139742.54759\Main.cc:33: error: 'swap' was not declared in this scope
F:\temp\16139742.54759\Main.cc: In function 'int main()':
F:\temp\16139742.54759\Main.cc:96: error: 'cin' was not declared in this scope
F:\temp\16139742.54759\Main.cc:101: error: 'memset' was not declared in this scope
F:\temp\16139742.54759\Main.cc:105: error: 'INT_MAX' was not declared in this scope
F:\temp\16139742.54759\Main.cc:110: error: 'scanf' was not declared in this scope
F:\temp\16139742.54759\Main.cc:111: error: expected primary-expression before '<' token
F:\temp\16139742.54759\Main.cc:111: error: 'span' was not declared in this scope
F:\temp\16139742.54759\Main.cc:111: error: expected ';' before 'style'
F:\temp\16139742.54759\Main.cc:117: error: 'scanf' was not declared in this scope
F:\temp\16139742.54759\Main.cc:132: error: 'sort' was not declared in this scope
F:\temp\16139742.54759\Main.cc:158: error: 'printf' was not declared in this scope
*/