本文共 1418 字，大约阅读时间需要 4 分钟。

题意：

两种操作

1：在x,y这个点上涂上颜色c。

2：查询1,y1和x,y2组成的矩形包含多少种颜色。

代码：

矩形区域查询点，赛时直接把之前cdq分治+bit的代码贴上然后开了50个树状数组去做，时间复杂度是n*logn*logn*50，直接十几e的复杂度，tle，而且因为树状数组的logn和50是不随数据变的，所以跑起来还没有暴力快，然后暴力代码ac了。。。

50种颜色其实很容易想到压缩一下，第i位表示第i种颜色是否存在，但是用树状数组的话就得去容次一下，然而|运算减法在这里明显是不满足的。但是加法是可以的呀，因为一个区间的子区间如果存在这种颜色，那么该区间也一定存在咯。然后就是这个题最重要的了，观察数据，每次查询都是x=1的情况，x=1的话，那么只要横坐标小于x的横坐标就满足情况了，可以用cdq分治把x这一维降下来，只要横坐标比询问的x小的就可以更新。

然后维护的时候用线段树，维护一个纵坐标区间内的颜色数量，这个值用一个long long值压缩就好。然后就cdq分治的套路了。

这个题的切入点感觉就是x=1上，一开始读完题就想着套之前代码值不对的，应该分析一下这个题改动的地方。

代码：

#include 
   
    #define lson o<<1#define rson o<<1|1#define MID int mid = (l+r)>>1;#define LL long long#define ps push_backusing namespace std;const int maxn=3e5+5;LL val[maxn<<2];void update(int o, int l, int r, int x, int c, int tp){    if(l==r)    {        if(tp==1)val[o]|=(1LL<
    
     mid)res|=sum(rson, mid+1, r, ll, rr);    return res;}struct node{    int id, qid, x, y1, y2, type, col;    bool operator <(const node &a)const     {        if(x!=a.x)return x
     
      >1;    cdq(l, mid);cdq(mid, r);    int p=l, q=mid, o=0;    while(p
      
       ls;int getid(int x){    return lower_bound(ls.begin(), ls.end(), x)-ls.begin()+1;}int main(){    int col, x, y1, y2, tp, id=1, qid=1, i, j;     while(~scanf("%d", &tp))    {        if(tp==0 || tp==3)        {            sort(ls.begin(), ls.end());            ls.erase(unique(ls.begin(), ls.end()), ls.end());            n=ls.size()+1;            for(i=1; i
      
     
    
   

转载地址：http://roywb.baihongyu.com/