网站建设.软件开发,个人网站需要备案,男的如何自己解决生理问题,安全网站建设题目链接 题意#xff1a; 有四种操作 0操作 清空所有点 1操作 在#xff08;x,y#xff09;处插入一个带颜色的点 2 操作统计(1~x)(y1~y2#xff09;这个范围的不同的颜色数 3 结束 思路#xff1a; 颜色数只有51个 我们可以建51颗线段树 因为每次查询都是1~x范围的 所以… 题目链接 题意 有四种操作 0操作 清空所有点 1操作 在x,y处插入一个带颜色的点 2 操作统计(1~x)(y1~y2这个范围的不同的颜色数 3 结束 思路 颜色数只有51个 我们可以建51颗线段树 因为每次查询都是1~x范围的 所以我们对于每个颜色的线段树 维护y轴的区间 节点的值维护区间最小的x 对于每次查询 我们就只需要查询 每种颜色是否有x的点即可 关于剪枝 TLE 7784MS 5584MS #includebits/stdc.h
using namespace std;
#define ll long long
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define inf 0x3f3f3f3f
const int maxn 10000005;
int cnt,x,fg;
int ls[maxn*4],rs[maxn*4],Min[maxn*4],root[60];
inline void init(){memset(root,0,sizeof(root));ls[0]0;rs[0]0;Min[0]inf;cnt0;
}
inline void push_up(int rt){Min[rt]min(Min[ls[rt]],Min[rs[rt]]);
}
inline void update(int rt,int l,int r,int L,int val){if(!rt){rtcnt;ls[rt]0;rs[rt]0;Min[rt]val;}if(lr){Min[rt]min(Min[rt],val);return ;}int m(lr)1;if(Lm) update(ls[rt],l,m,L,val);else update(rs[rt],m1,r,L,val);push_up(rt);
}
inline void query(int rt,int l,int r,int L,int R){if(fg||!rt) return ;if(LlrR) {if(Min[rt]x) fg1;return ;}int m(lr)1;if(Lm) query(ls[rt],l,m,L,R);if(Rm) query(rs[rt],m1,r,L,R);
}
int main(){int op,y,c,l,r;int nmaxn;while(~scanf(%d,op)){if(op3) break;if(op0){init();}else if(op1){scanf(%d %d %d,x,y,c);update(root[c],1,n,y,x);}else {scanf(%d %d %d,x,l,r);int ans0;for(int i0;i50;i){fg0;query(root[i],1,n,l,r);ansfg;}printf(%d\n,ans);}}return 0;
} View Code 距离省赛越来越近 又要被暴打了大雾 转载于:https://www.cnblogs.com/MengX/p/11291321.html
