[hdu6183][Color it]

题目链接

题目大意

有一个矩阵,总共有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;
}
上一篇:Android.15.Fragment


下一篇:Spring environment 和 applicationContext