题意：给定n个区间，每个区间有颜色。m次询问，每次询问：这n个区间中所有被包含在[x, y]这一区间中的区间，它们的颜色是否取遍了[l, r]中的所有颜色。

强制在线。

解：第一步是大家都熟悉的套路⑧，把这些区间按照左端点排序。

然后从右往左加区间，用一个可持久化数据结构维护答案。

然后我在这里就被套路住了......一般来说是线段树上x维护右端点为x的答案。但是本题要把第二维换一下。

主席树的版本仍旧是左端点。但是线段树上每个位置维护的是该颜色的区间，结尾的最小值。

然后查询，我们就查对应版本对应颜色区间的全体最大值是否大于y。大于y表示那个颜色无解。输出no。否则输出yes。

1 #include 
      
        2  3 const int N = 300010, M = 20000010, INF = 0x7f7f7f7f; 4  5 struct Node { 6     int l, r, c; 7     inline bool operator <(const Node &w) const { 8         return l < w.l; 9     }10 }node[N];11 12 int ls[M], rs[M], large[M], tot;13 int xx, q, n, lm, X[N], rt[N];14 15 void insert(int &x, int y, int p, int v, int l, int r) {16     if(!x || x == y) {17         x = ++tot;18         ls[x] = ls[y];19         rs[x] = rs[y];20         large[x] = large[y];21     }22     if(l == r) {23         large[x] = std::min(large[x], v);24         return;25     }26     int mid = (l + r) >> 1;27     if(p <= mid) insert(ls[x], ls[y], p, v, l, mid);28     else insert(rs[x], rs[y], p, v, mid + 1, r);29     large[x] = std::max(large[ls[x]], large[rs[x]]);30     //printf("[%d %d] large = %d \n", l, r, large[x]);31     return;32 }33 34 int ask(int L, int R, int l, int r, int o) {35     if(!o) return INF;36     if(L <= l && r <= R) return large[o];37     int mid = (l + r) >> 1, ans = -INF;38     if(L <= mid) ans = std::max(ans, ask(L, R, l, mid, ls[o]));39     if(mid < R) ans = std::max(ans, ask(L, R, mid + 1, r, rs[o]));40     return ans;41 }42 43 int main() {44     memset(large, 0x7f, sizeof(large));45     scanf("%d%d%d", &lm, &q, &n);46     for(int i = 1; i <= n; i++) {47         scanf("%d%d%d", &node[i].l, &node[i].r, &node[i].c);48         X[i] = node[i].l;49     }50     std::sort(node + 1, node + n + 1);51     std::sort(X + 1, X + n + 1);52     xx = std::unique(X + 1, X + n + 1) - X - 1;53     for(int i = n; i >= 1; i--) {54         node[i].l = std::lower_bound(X + 1, X + xx + 1, node[i].l) - X;55         /// build56         insert(rt[node[i].l], rt[node[i].l + 1], node[i].c, node[i].r, 1, lm);57         //printf("insert %d %d rt[%d] \n", node[i].c, node[i].r, node[i].l);58     }59 60     /*printf("X : ");61     for(int i = 1; i <= xx; i++) {62         printf("%d ", X[i]);63     }64     puts("");*/65 66     for(int i = 1, x, y, l, r; i <= q; i++) {67         scanf("%d%d%d%d", &l, &r, &x, &y);68         int t = std::lower_bound(X + 1, X + xx + 1, x) - X;69 70         //printf("i = %d  t = %d \n", i, t);71 72         if(t > xx) {73             printf("no\n");74             //printf("ERROR 1 \n");75         }76         else {77             t = ask(l, r, 1, lm, rt[t]);78             if(t > y) printf("no\n");79             else printf("yes\n");80             //printf("t = %d \n", t);81         }82         fflush(stdout);83     }84 85     return 0;86 }