• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

F. MEX Queries

题意

将间隔l r设置为1。

将间隔l r设置为0

L r翻转间隔l r(即1-0或0-1)

每次运算后找到值为0的最左边的位置号。

思路

用段树维护区间和

用懒人标记当前节点,置1,置0,翻转或者不需要操作(降低时间复杂度)

对于翻转操作,每次更新懒人节点时,需要判断之前的懒人是什么,然后根据之前的懒人和新分配的懒人给出一个新的懒人。

零和一运算可以直接更新lazy。

更新间隔总和:

设置为零:tree。sum=0;

Set: tree 。sum=tree 。r树。L1;(区间长度为区间和)

翻转:树。sum=tree 。r树。L1树[我]。总和;(间隔长度减去原始间隔总和就是新的间隔总和)

最后,在查询整个区间查询的时候,要调低lazy的信息(如果要访问,必须调低lazy的信息;如果接入,暂时不需要降低)。

离散化:

因为给定的数据l r会非常大,可以达到1e18(肯定tle)而运算次数只有1e5,所以需要离散化。

每次的答案只能给L或者r ^ 1或者1,所以只要把L,r ^ 1,1放入数组进行离散化就可以了。因为R时间的区间边界用于查询更新等操作,所以也要放入数组。

然后对数组进行排序、离散化和去重,离散化数组中l r的位置区间作为对应区间处理。

#includebits/stdc。h

#includeunordered_map

#定义ll long long

#定义全无符号长整型

#定义IOS IOS :3360 sync _ with _ stdio(false);CIN . tie(0);cout . tie(0);

使用命名空间std

const ll INF=0x 3 F3 F3 f 3 f;

const ll INF=0x 3 F3 F3 F3 F3 f 3 f;

const double EPS=1e-4;

const ll N=1e 18 5;

const int M=1e5 5

const int mod=1e 9 7;

ll n,op[M],l[M],r[M],a[M * 3],b[M * 3];//一定要打开三次,因为每次都要放在l r r 1里

mapll,llmp

结构节点{

ll l,r,sum,懒;

}树[M * 12];//一般段树需要开4次,这里需要乘以3(l r r 1),所以是12次。

void push_up(ll p) {

树[p]。sum=tree[p 1]。sum树[p 1|1]。总和;

}

//下面的操作

void下推(ll p) {

if(树[p].lazy==-1)返回;

If(树[p].lazy==1) {//如果父节点lazy设置为1左右,则子节点lazy直接设置为1

树[第1页]。懒=树[p]。懒惰;

树[p 1 | 1]。懒=树[p]。懒惰;

树[第1页]。sum=tree[p 1]。r树[p 1]。L1;

树[p 1 | 1]。sum=tree[p 1 | 1]。r树[p 1 | 1]。L1;

}

Else if (tree[p].lazy==0) {//如果父节点lazy设置为0左右,子节点lazy直接设置为0。

树[第1页]。懒=树[p]。懒惰;

树[p 1 | 1]。懒=树[p]。懒惰;

树[第1页]。sum=tree[p 1 | 1]。sum=0;

}

Else {//如果父节点lazy翻转,则判断子节点前的lazy标记,并相应翻转。

//每次先更新子节点的sum值,否则会有多个懒值重叠,但是sum值还没有更新。

树[第1页]。sum=tree[p 1]。r树[p 1]。l 1 - tree[p 1]。总和;

树[p 1|1]。sum=tree[p 1|1]。

r - tree[p << 1|1].l + 1 - tree[p << 1|1].sum; ll x = tree[p << 1].lazy; if (x == 0) tree[p << 1].lazy = 1;//之前lazy是0 就标记成1 else if (x == 1) tree[p << 1].lazy = 0;//之前lazy是1 就标记成0 else if (x == 3) tree[p << 1].lazy = -1;//之前lazy是翻转 就不用变 else tree[p << 1].lazy = 3;//之前lazy是未标记 就标记成翻转 x = tree[p << 1 | 1].lazy; if (x == 0) tree[p << 1 | 1].lazy = 1; else if (x == 1) tree[p << 1 | 1].lazy = 0; else if (x == 3) tree[p << 1 | 1].lazy = -1; else tree[p << 1 | 1].lazy = 3; } tree[p].lazy = -1;//下放父亲节点后 lazy置为未标记 } void build(ll l, ll r, ll p) { tree[p].l = l; tree[p].r = r; tree[p].lazy = -1;//放在if外面 每个结点的lazy都要初始化为-1 if (l == r) { tree[p].sum = 0; return; } ll mid = (l + r) / 2; build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1); push_up(p); } void update1(ll xl, ll xr, ll p) { ll l = tree[p].l, r = tree[p].r; if (l >= xl && r <= xr) { tree[p].sum = r - l + 1; tree[p].lazy = 1; return; } push_down(p);//更新完一个结点就下放一下信息 ll mid = (l + r) / 2; if (mid >= xl) update1(xl, xr, p << 1); if (mid < xr) update1(xl, xr, p << 1 | 1); push_up(p); } void update2(ll xl, ll xr, ll p) { ll l = tree[p].l, r = tree[p].r; if (l >= xl && r <= xr) { tree[p].sum = 0; tree[p].lazy = 0; return; } push_down(p); ll mid = (l + r) / 2; if (mid >= xl) update2(xl, xr, p << 1); if (mid < xr) update2(xl, xr, p << 1|1); push_up(p); } void update3(ll xl, ll xr, ll p) { ll l = tree[p].l, r = tree[p].r; if (l >= xl && r <= xr) { //先更新sum避免后面没更新 tree[p].sum = tree[p].r - tree[p].l + 1 - tree[p].sum; //对于lazy更新要结合之前的lazy标记 if (tree[p].lazy == 0) tree[p].lazy = 1; else if (tree[p].lazy == 1) tree[p].lazy = 0; else if (tree[p].lazy == -1) tree[p].lazy = 3; else tree[p].lazy = -1; return; } push_down(p); ll mid = (l + r) / 2; if (mid >= xl) update3(xl, xr, p << 1); if (mid < xr) update3(xl, xr, p << 1|1); push_up(p); } ll query(ll p) { ll l = tree[p].l, r = tree[p].r; if (l == r) return b[l]; push_down(p); if (tree[p << 1].sum < (l + r) / 2 - l + 1) return query(p << 1); else return query(p << 1|1); } void solve() { cin >> n; ll tot = 0; for (int i = 1; i <= n; i++) { cin >> op >> l >> r; b[++tot] = l; b[++tot] = r; b[++tot] = r + 1; } b[++tot] = 1; sort(b + 1, b + 1 + tot);//排序 ll len = unique(b + 1, b + (ll)1 + tot) - b - 1;//离散化去重 for (int i = 1; i <= len; i++) //离散化对应 mp[b] = i; build(1, len, 1); for (int i = 1; i <= n; i++) { if (op == 1) update1(mp[l], mp[r], 1); else if (op == 2) update2(mp[l], mp[r], 1); else update3(mp[l], mp[r], 1); cout << query(1) << "\n"; } } signed main() { IOS; int t = 1; //cin >> t; while (t--) { solve(); } }
Link to comment
Share on other sites