自助建站系统网站建设开发,济南市莱芜区招聘信息,页面设计器,新开传奇网站超变文章目录题意思路传送门
题意
有nnn个人#xff0c;给你qqq个请求#xff0c;分以下三种#xff1a; [l,r,x][l,r,x][l,r,x] 如果x0x0x0#xff0c;代表[l,r][l,r][l,r]这个区间内的人都没病。[l,r,x][l,r,x][l,r,x] 如果x1x1x1#xff0c;代表[l,r][l,r][l,r]这个区间内…
文章目录题意思路传送门
题意
有nnn个人给你qqq个请求分以下三种
[l,r,x][l,r,x][l,r,x] 如果x0x0x0代表[l,r][l,r][l,r]这个区间内的人都没病。[l,r,x][l,r,x][l,r,x] 如果x1x1x1代表[l,r][l,r][l,r]这个区间内的人至少一个有病。jjj 查询第jjj个人是否能确定有病或者没病如果能确定那么是有病还是没病。
1≤n,q≤2e51\le n,q\le 2e51≤n,q≤2e5
思路
一个人没病很好确定考虑一个人有病怎么确定呢
对于t1t1t1的时候如果这个区间内的没病的人数等于区间长度减111那么剩下那个人一定有病否则就不能确定。
让后这个题的一个比较难的点是假设当前是第iii个询问你需要根据前iii个询问的信息来回答当前的答案在线很难我们不妨离线来搞。
离线来的话对于每个没病的人都记一下这个位置确定的最小时间显然势能线段树即可。让后再从头遍历一下x1x1x1的信息首先查询一下当前区间没病的人是否等于区间长度减111让后再看一下区间最大值是否小于当前询问时间iii都满足的话找到剩余的这个人的位置将ans[pos]min(ans[pos],max(i,mx))ans[pos]min(ans[pos],max(i,mx))ans[pos]min(ans[pos],max(i,mx))即可。
再处理查询根据上面的信息分情况即可。
复杂度O(nlogn)O(nlogn)O(nlogn)。
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define pb push_back
using namespace std;const int N200010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,qq;
int ans[N];
struct Query {int op,l,r,x;
}q[N];
struct Node {int l,r;int cnt,mx;int id;
}tr[N2];void pushup(int u) {tr[u].cnttr[L].cnttr[R].cnt;tr[u].mxmax(tr[L].mx,tr[R].mx);if(tr[L].id!0) tr[u].idtr[L].id;else if(tr[R].id!0) tr[u].idtr[R].id;else tr[u].id0;
}void build(int u,int l,int r) {tr[u]{l,r,0,-1,0};if(lr) {tr[u].idl;return;}build(L,l,Mid); build(R,Mid1,r);pushup(u);
}void change(int u,int l,int r,int x) {if(tr[u].cntLen(u)) return;if(tr[u].ltr[u].r) {tr[u].cnt1;tr[u].mxx;tr[u].id0;return;}if(lMid) change(L,l,r,x);if(rMid) change(R,l,r,x);pushup(u);
}int query_cnt(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u].cnt;int ans0;if(lMid) ansquery_cnt(L,l,r);if(rMid) ansquery_cnt(R,l,r);return ans;
}int query_max(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u].mx;int ans-1;if(lMid) ansmax(ans,query_max(L,l,r));if(rMid) ansmax(ans,query_max(R,l,r));return ans;
}Node query_id(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u];if(rMid) return query_id(L,l,r);if(lMid) return query_id(R,l,r);Node ans,ls,rs;lsquery_id(L,l,r);rsquery_id(R,l,r);ans.cntls.cntrs.cnt;ans.mxmax(ls.mx,rs.mx);if(ls.id!0) ans.idls.id;else if(rs.id!0) ans.idrs.id;else ans.id0;/*if(ls.cntls.r-ls.l1rs.cntrs.r-rs.l1) ans.id0;else if(ls.cnt!ls.r-ls.l1) ans.idls.id;else ans.idrs.id;ans.lls.l; ans.rrs.r;*/return ans;
}void solve() {scanf(%d%d,n,qq);build(1,1,n);for(int i1;in;i) ans[i]qq1;for(int i1;iqq;i) {int op; scanf(%d,op);if(op0) {int l,r,x; scanf(%d%d%d,l,r,x);q[i]{op,l,r,x};if(x0) change(1,l,r,i);} else {int x; scanf(%d,x);q[i]{op,-1,-1,x};}}for(int i1;iqq;i) {if(q[i].op0q[i].x1) {int lq[i].l,rq[i].r;int mxquery_max(1,l,r);int cntquery_cnt(1,l,r);if(cnt!r-l) continue;Node resquery_id(1,l,r);ans[res.id]min(ans[res.id],max(mx,i));//cout**ans[res.id]endl;}}for(int i1;iqq;i) {if(q[i].op1) {int xq[i].x;int cntquery_cnt(1,x,x);int mxquery_max(1,x,x);if(cntmxi) puts(NO);else {if(ans[x]i) puts(N/A);else puts(YES);}}}
}int main() {int _1;while(_--) {solve();}return 0;
}
/*
0 4 5 0
1 5
1 6
0 4 6 1
1 6
0 2 5 1
0 2 2 0
1 3
1 21 2 3 4 5 6
1 0 1 0 0 1
*/
