题目链接

题目大意

有一个矩阵，总共有4种操作

0:清空这个矩阵

1 x y c:将\((x,y)(1 \leq x ,y\leq 10^6)\)这个点加上一种颜色c\((0\leq c \leq 50)\)(注意是加上，也就是之前的颜色不会被覆盖)

2 x y1 y2:查询左上角为\((1,y1)\)，右下角为\((x,y2)\)的矩阵中的颜色个数。

3:结束程序

0操作不超过10次，1操作和2操作不超过150000次

思路

先考虑空间足够的情况下应该怎么做。对于每个颜色开一个线段树。第i个位置储存，这个颜色中第i列最小的x是多少，因为每次查询都是从(1,y1)到(x,y2)，所以查询一种颜色的时候，只要看从y1到y2中最小的值是不是比x小就行了，如果比x小，就说明存在这种颜色。

上面的空间复杂度为\(50*10^6\)，空间不够，所以考虑动态开点线段树。记录下每种颜色的根，然后分别动态开点插入即可。空间复杂度\((nlogn)　n=150000\)

直接正常查询对于这道题是会超时的，所以要优化一下。也就是如果当前找到这种颜色了，就退出就行了。

代码

/*

* @Author: wxyww

* @Date:   2018-12-10 10:39:02

* @Last Modified time: 2018-12-10 11:20:39

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<ctime>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 200000 + 100,INF = 1e7,M = 1e6;

ll read() {

   ll 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;

}

int tree[N * 20],ls[N * 20],rs[N * 20],root[55];

int num;

void update(int &rt,int l,int r,int pos,int c) {

   if(!rt) {

      rt = ++num;

      tree[rt] = c;

   }

   tree[rt] = min(tree[rt],c);

   if(l == r) return;

   int mid = (l + r) >> 1;

   if(pos <= mid) update(ls[rt],l,mid,pos,c);

   else update(rs[rt],mid + 1,r,pos,c);

}

int tag,cx;

void query(int rt,int l,int r,int L,int R) {

   if(!rt || tag) return;

   if(L <= l && R >= r) {

      if(tree[rt] <= cx) tag = 1;

      return;

   }

   int mid = (l + r) >> 1;

   if(L <= mid) query(ls[rt],l,mid,L,R);

   if(R > mid)  query(rs[rt],mid + 1,r,L,R);

}

int main() {

   while(1) {

      int opt = read();

      if(opt == 3) return 0;

      if(opt == 0) {

         memset(tree,0x3f,sizeof(tree));

         memset(root,0,sizeof(root));

         num = 0;

         memset(ls,0,sizeof(ls));

         memset(rs,0,sizeof(rs));

      }

      if(opt == 1) {

         int x = read(),y = read(),c = read();

         update(root[c],1,M,y,x);

      }

      if(opt == 2) {

         cx = read();int y1 = read(),y2 = read();

         int ans = 0;

         for(int i = 0;i <= 50;++i) {

            tag = 0;

            query(root[i],1,M,y1,y2);

            ans += tag;

         }

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

      }

   }

   return 0;

}