2018牛客多校第六场 I.Team Rocket

题意：

　　给出n个区间和m个点（点按顺序给出且强制在线）。每个区间只会被第一个他包含的点摧毁。问每个点能摧毁多少个区间以及每个区间是被哪个点摧毁的。

题解：

　　将n个区间按照左端点排序，然后用vector（储存左端点，右端点，id）初始化线段树。

　　初始化的方法是：对于线段树的n个叶子节点，即为排好序的n个区间。对于其他节点，将左右儿子按照右端点大小归并（归并是线性复杂度）。

　　还要维护每个节点左端点的最小值（用来剪枝）和最大值（用来判断可行性）。

　　每个区间只会被第一个他包含的点摧毁，所以用vis数组标记一个区间是否已被摧毁。

　　每次遍历vector数组后使用erase会T掉，可以再维护一个信息表示上次遍历到的位置，这次从这个位置开始遍历。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

const int mod = ;

int t, n, m;

int x, y, lst, judge;

int ans[N], vis[N];

struct node {

    int l, r, id;

    bool operator < (const node &a) {

        return l == a.l ? r > a.r : l < a.l;

    }

}a[N];

int min_L[N<<], max_L[N<<], L[N<<];

vector<node> g[N<<];

void merge(int id) {

    int lch = id<<, rch = id<<|;

    max_L[id] = max(max_L[lch], max_L[rch]);

    min_L[id] = min(min_L[lch], min_L[rch]);

    int len1 = g[lch].size(), len2 = g[rch].size();

    int l1 = , l2 = ;

    while(l1 < len1 || l2 < len2) {

        if(l1 == len1 || l2 != len2 && g[rch][l2].r > g[lch][l1].r) g[id].push_back(g[rch][l2++]);

        else g[id].push_back(g[lch][l1++]);

    }

}

void build(int id, int l, int r) {

    g[id].clear();

    L[id] = ;

    if(l == r) {

        g[id].push_back(a[l]);

        max_L[id] = min_L[id] = a[l].l;

        return ;

    }

    int mid = l+r >> ;

    build(id<<, l, mid);

    build(id<<|, mid+, r);

    merge(id);

}

int query(int id, int l, int r, int ql, int num) {

    if(min_L[id] > ql) return ;

    if(max_L[id] <= ql) {

        int cnt = L[id], tot = ;

        int len = g[id].size();

        while(cnt < len && g[id][cnt].r >= ql) {

            int v = g[id][cnt].id;

            if(!vis[v]) {

                lst = 1ll*lst*v%mod;

                judge++;

                ans[v] = num;

                vis[v] = ;

                tot++;

            }

            cnt++;

        }

        L[id] = cnt;

        return tot;

    }

    int res = ;

    int mid = l+r>>;

    res += query(id<<, l, mid, ql, num);

    res += query(id<<|, mid+, r, ql, num);

    return res;

}

int main() {

    scanf("%d", &t);

    for(int casee = ; casee <= t; casee++) {

        printf("Case #%d:\n", casee);

        scanf("%d%d", &n, &m);

        for(int i = ; i <= n; i++) {

            scanf("%d%d", &a[i].l, &a[i].r);

            ans[i] = vis[i] = ;

            a[i].id = i;

        }

        sort(a+, a+n+);

        build(, , n);

        lst = ;

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

            scanf("%d", &y);

            x = y^(lst % mod);

            lst = , judge = ;

            printf("%d\n", query(, , n, x, i));

            if(!judge) lst = ;

        }

        for(int i = ; i < n; i++) printf("%d ", ans[i]);

        printf("%d\n", ans[n]);

    }

}