Problem 2 线段树
2024-10-20 16:21:52
$des$
一个无限长的 01 序列，初始全为 0，每次选择一个区间 [l,r] 进行操作，有三种操作：
1. l r 将 [l,r] 中所有元素变成 1。
2. l r 将 [l,r] 中所有元素变成 0。
3. l r 将 [l,r] 中所有元素异或上 1。
每次操作后询问最左边的 0 在哪个位置.
$sol$
线段树
将所有可能成为答案的点加入线段树的根节点维护
$code$
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <cstring> using namespace std; #define LL long long
#define Rep(i, a, b) for(int i = a; i <= b; i ++)
#define gc getchar() inline LL read() {
LL x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} const int N = 1e5 + , M = N * * ; struct Node {
LL opt, l, r;
} Ask[N];
LL A[M], js;
int n; struct Node_ {
int Cnt[][M << ], Size[M << ], F[M << ]; #define lson jd << 1
#define rson jd << 1 | 1 void Build_tree(int l, int r, int jd) {
F[jd] = -;
Size[jd] = r - l + ;
Cnt[][jd] = Size[jd];
if(l == r) return ;
int mid = (l + r) >> ;
Build_tree(l, mid, lson), Build_tree(mid + , r, rson);
} void Push_down(int jd) {
int f = F[jd];
if(f == ) {
F[lson] = F[rson] = ;
Cnt[][lson] = Size[lson], Cnt[][rson] = Size[rson];
Cnt[][lson] = , Cnt[][rson] = ;
F[jd] = -;
} else if(f == ) {
F[lson] = F[rson] = ;
Cnt[][lson] = Size[lson], Cnt[][rson] = Size[rson];
Cnt[][lson] = , Cnt[][rson] = ;
F[jd] = -;
} else {
if(F[lson] == ) {
swap(Cnt[][lson], Cnt[][lson]);
F[lson] = -;
} else {
if(F[lson] == -) {
F[lson] = ;
swap(Cnt[][lson], Cnt[][lson]);
} else if(F[lson] == ) {
F[lson] = ;
Cnt[][lson] = Size[lson], Cnt[][lson] = ;
} else {
F[lson] = ;
Cnt[][lson] = Size[lson], Cnt[][lson] = ;
}
}
if(F[rson] == ) {
swap(Cnt[][rson], Cnt[][rson]);
F[rson] = -;
} else {
if(F[rson] == -) {
F[rson] = ;
swap(Cnt[][rson], Cnt[][rson]);
} else if(F[rson] == ) {
F[rson] = ;
Cnt[][rson] = Size[rson], Cnt[][rson] = ;
} else {
F[rson] = ;
Cnt[][rson] = Size[rson], Cnt[][rson] = ;
}
}
F[jd] = -;
}
} void Sec_G(int l, int r, int jd, int x, int y, int num){
if(x <= l && r <= y) {
Cnt[num][jd] = Size[jd];
Cnt[num ^ ][jd] = ;
F[jd] = num;
// cout << Cnt[1][jd] << " " << Cnt[0][jd] << "\n";
return ;
}
if(F[jd] != -) Push_down(jd);
int mid = (l + r) >> ;
// cout << Cnt[0][lson] << "\n";
if(x <= mid) Sec_G(l, mid, lson, x, y, num);
if(y > mid) Sec_G(mid + , r, rson, x, y, num);
Cnt[][jd] = Cnt[][lson] + Cnt[][rson];
Cnt[][jd] = Cnt[][lson] + Cnt[][rson];
} int Ask(int l, int r, int jd) {
if(l == r) {
return l;
}
if(F[jd] != -) Push_down(jd);
int mid = (l + r) >> ;
// cout << Cnt[0][lson] << "\n";
if(Cnt[][lson]) return Ask(l, mid, lson);
else return Ask(mid + , r, rson);
} void Seg_fz(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) {
if(F[jd] == -) {
swap(Cnt[][jd], Cnt[][jd]);
F[jd] = ;
return ;
} else if(F[jd] == ) {
F[jd] = ;
Cnt[][jd] = Size[jd];
Cnt[][jd] = ;
} else if(F[jd] == ) {
F[jd] = ;
Cnt[][jd] = ;
Cnt[][jd] = Size[jd];
} else {
F[jd] = -;
swap(Cnt[][jd], Cnt[][jd]);
}
return ;
}
if(F[jd] != -) Push_down(jd);
int mid = (l + r) >> ;
// cout << Cnt[0][lson] << "\n";
if(x <= mid) Seg_fz(l, mid, lson, x, y);
if(y > mid) Seg_fz(mid + , r, rson, x, y);
Cnt[][jd] = Cnt[][lson] + Cnt[][rson];
Cnt[][jd] = Cnt[][lson] + Cnt[][rson];
}
} Segtree; inline LL Getans() {
int w = Segtree.Ask(, js, );
// if(A[w - 1] + 1 != A[w]) return A[w - 1] + 1;
// else return A[w];
return A[w];
} int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
n = read();
Rep(i, , n) {
LL opt = read(), l = read(), r = read();
A[++ js] = l, A[++ js] = r; A[++ js] = max(1ll, l - ), A[++ js] = r + ;
Ask[i] = (Node) {
opt, l, r
};
}
A[++ js] = ;
sort(A + , A + js + );
js = unique(A + , A + js + ) - A - ;
Segtree.Build_tree(, js, );
// Rep(i, 1, 10) cout << Segtree.F[i] << " ";
// return 0;
Rep(i, , n) {
LL opt = Ask[i].opt, l = Ask[i].l, r = Ask[i].r;
int wl = lower_bound(A + , A + js + , l) - A;
int wr = lower_bound(A + , A + js + , r) - A;
if(opt == ) {
Segtree.Sec_G(, js, , wl, wr, );
cout << Getans() << "\n";
} else if(opt == ) {
Segtree.Sec_G(, js, , wl, wr, );
cout << Getans() << "\n";
} else {
Segtree.Seg_fz(, js, , wl, wr);
cout << Getans() << "\n";
}
} return ;
}
最新文章
- 线程，yield让出cpu调度
- 增量式PID简单翻板角度控制
- CKEditor的使用方法
- hibernate初步4
- c++ initialize_list
- MyEclipse导入Maven项目
- 把centos 的mysql 重装一下 把原来的lnmp删除，怎么备份还原数据库
- Leetcode-Construct Binary Tree from inorder and preorder travesal
- java文件IO操作
- xhEditor struts2实现图片上传
- Linux系统开机启动流程
- HandsonTable日期控件的汉化
- poj 2886 线段树+反素数
- MySQL在删除表时I/O错误原因分析
- oo第四次博客
- Django 缓存
- JS 作用域及作用域链
- less和sass的定义和区别
- Chapter3_操作符_关系操作符
- Postgres使用ALTER USER命令修改用户的密码、密码过期，锁定，解锁