更好的阅读体验（NC 博客图炸得稀烂）

$\mathtt{\text{First}}\mathtt{\text{Things}}\mathtt{\text{First}}\backslash texttt\{First\; Things\; First\}$

p.s.：图没截全，出题人回复了我一个 ^_^。

$\mathtt{\text{Description}}\backslash texttt\{Description\}$

题目传送门

形式化题意（将询问转化成了求关键步骤而并非原询问，需要将该关键步骤的答案经过简单处理才能得到原询问答案）

• 你有两个 $\mathtt{\text{01}}\backslash texttt\{01\}$ 串 $aa$ 和 $bb$，下标从 $11$ 开始，初始均为 $00$.

  对于 $aa$ 串有 $nn$ 个操作，第 $ii$ 次操作 ${\text{opa}}_i\backslash text\{opa\}\_i$ 为：

  • ${\text{la}}_i{\text{ra}}_i\backslash text\{la\}\_i\backslash texttt\{\; \}\backslash text\{ra\}\_i$，把 $a_{{\text{la}}_i}\sim a_{{\text{ra}}_i}a\_\{\backslash text\{la\}\_i\}\backslash sim\; a\_\{\backslash text\{ra\}\_i\}$ 赋值成 $11$。

  对于 $bb$ 串也有 $nn$ 个操作，第 $ii$ 次操作 ${\text{opb}}_i\backslash text\{opb\}\_i$ 为：

  • ${\text{lb}}_i{\text{rb}}_i\backslash text\{lb\}\_i\backslash texttt\{\; \}\backslash text\{rb\}\_i$，把 $b_{{\text{lb}}_i}\sim b_{{\text{rb}}_i}b\_\{\backslash text\{lb\}\_i\}\backslash sim\; b\_\{\backslash text\{rb\}\_i\}$ 赋值成 $11$。

  你还有 $nn$ 个询问，对于第 $ii$ 次询问 ${\text{query}}_i\backslash text\{query\}\_i$，先执行操作 ${\text{opa}}_i\backslash text\{opa\}\_i$ 和 ${\text{opb}}_i\backslash text\{opb\}\_i$（前 $i-1i-1$ 次询问执行的操作仍然会被保留），再求 $aa$ 和 $bb$ 左起（即以 $a_1,b_{1}a\_1,b\_1$ 为起点）最长的连续的 $11$ 的长度 ${\text{lena}}_i\backslash text\{lena\}\_i$ 和 ${\text{lenb}}_i\backslash text\{lenb\}\_i$。

• $1\le n\le 10^{5}1\backslash le\; n\backslash le\; 10^5$，$1\le {\text{la}}_i\le {\text{ra}}_i\le 10^{9}1\backslash le\; \backslash text\{la\}\_i\backslash le\; \backslash text\{ra\}\_i\backslash le\; 10^9$，$1\le {\text{lb}}_i\le {\text{rb}}_i\le 10^{9}1\backslash le\; \backslash text\{lb\}\_i\backslash le\; \backslash text\{rb\}\_i\backslash le\; 10^9$。

$\mathtt{\text{Solution}}\backslash texttt\{Solution\}$

前置知识：珂朵莉树。

上面的题意已经转化得差不多了。看到区间赋值的操作，当然要想起珂愛的珂朵莉树，这是珂朵莉树最基础的操作之一。

其次考虑如何求左起最长连续的 $11$ 的长度，因为是左起，所以区间长度就是右端点编号。可以从 set 的 begin 开始遍历直到 set 的 end，一旦遍历到 $00$ 的颜色段，就将答案设置成当前区间的左端点 $l-1l-1$（因为 $l-1l-1$ 是最后一个 $11$ 的位置）。

然后你会发现：

因为每次从头开始遍历效率太低，珂朵莉树本身就是一种暴力数据结构，根本不能接受。

注意到只有区间赋值成 $11$ 的操作，这意味着 ${\text{lena}}_i\backslash text\{lena\}\_i$ 和 ${\text{lenb}}_i\backslash text\{lenb\}\_i$ 单调非降，因此只需要从上一次找到的右端点 $rr$ 往后找就行了，具体实现方法是从 split(ans+1) 的迭代器（$\text{ans}\backslash text\{ans\}$ 是上一次询问的答案）开始遍历。

时间复杂度为 $\mathcal{O}(\mathrm{玄}\mathrm{学}+\mathrm{珂}\mathrm{愛}+\mathrm{可}\mathrm{过})\backslash mathcal\{O\}(玄学+珂愛+可过)$，空间复杂度为 $\mathcal{O}(n)\backslash mathcal\{O\}(n)$，可以接受~~（这么珂愛的珂朵莉谁不会接受呢？）~~。

$\mathtt{\text{Code}}\backslash texttt\{Code\}$

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2", 3)
#pragma GCC target("avx","sse2")
//卡常
#include<bits/stdc++.h>
#define N 100005
#define lim 1000000000
using namespace std;
int n;
struct tool{
    int l,r;
}a[N],b[N];
struct node{
    int l,r,v;
    bool operator<(const node&b)const{
        return l<b.l;
    }
};
struct odt{
    set<node>s;
    int ans;
    auto split(int x){
        if(x>lim){
            return s.end();
        }
        auto it=s.lower_bound({x,0,0});
        if(it!=s.end()&&it->l==x){
            return it;
        }
        node t=*(--it);
        s.erase(it);
        s.insert({t.l,x-1,t.v});
        return s.insert({x,t.r,t.v}).first;
    }
    void assign(int l,int r){
        auto qr=split(r+1),ql=split(l);
        s.erase(ql,qr);
        s.insert({l,r,1});
    }
    int query(){
        for(auto it=split(ans+1);it!=s.end();++it){
            if(!it->v){
                return ans=it->l-1;
            }
        }
        return ans=lim;
    }
}sa,ya;
int main(){
    sa.s.insert({1,lim,sa.ans=0});
    ya.s.insert({1,lim,ya.ans=0});
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    for(int i=1;i<=n;++i){
        scanf("%d%d",&b[i].l,&b[i].r);
    }
    for(int i=1;i<=n;++i){
        sa.assign(a[i].l,a[i].r);
        ya.assign(b[i].l,b[i].r);
        int u=sa.query(),v=ya.query();
        if(u>v){
            cout<<"sa_win!\n"<<u-v<<'\n';
        }else if(u^v){
            cout<<"ya_win!\n"<<v-u<<'\n';
        }else{
            cout<<"win_win!\n0\n";
        }
    }
}

评测记录

$\mathtt{\text{The}}\mathtt{\text{End}}\backslash texttt\{The\; End\}$

$\text{『在太阳西斜的这个世界里』}\backslash Huge\; \backslash text\{『在太阳西斜的这个世界里』\}$

$\text{-Broken Chronograph-}\backslash Huge\; \backslash text\{-Broken\; Chronograph-\}$

$\text{『置身天上之森』}\backslash Huge\; \backslash text\{『置身天上之森』\}$

$\text{-Late Autumn Night′s Dream-}\backslash Huge\; \backslash text\{-Late\; Autumn\; Night\prime s\; Dream-\}$

$\text{『等这场战争结束之后』}\backslash Huge\; \backslash text\{『等这场战争结束之后』\}$

$\text{-Starry Road To Tomorrow-}\backslash Huge\; \backslash text\{-Starry\; Road\; To\; Tomorrow-\}$

$\text{『不归之人与望眼欲穿的人们』}\backslash Huge\; \backslash text\{『不归之人与望眼欲穿的人们』\}$

$\text{-Dice In Pot-}\backslash Huge\; \backslash text\{-Dice\; In\; Pot-\}$

$\text{『人人本着正义之名』}\backslash Huge\; \backslash text\{『人人本着正义之名』\}$

$\text{-From Down Till Dusk-}\backslash Huge\; \backslash text\{-From\; Down\; Till\; Dusk-\}$

$\text{『长存不灭的过去，逐渐消逝的未来』}\backslash Huge\; \backslash text\{『长存不灭的过去，逐渐消逝的未来』\}$

$\text{-No News Was Good News-}\backslash Huge\; \backslash text\{-No\; News\; Was\; Good\; News-\}$

$\text{『我回来了』}\backslash Huge\; \backslash text\{『我回来了』\}$

$\text{-Home,Sweet Home-}\backslash Huge\; \backslash text\{-Home,Sweet\; Home-\}$

$\text{『纵使日薄西山』}\backslash Huge\; \backslash text\{『纵使日薄西山』\}$

$\text{-Slight Light,Slight Hope-}\backslash Huge\; \backslash text\{-Slight\; Light,Slight\; Hope-\}$

$\text{『即使看不到未来』}\backslash Huge\; \backslash text\{『即使看不到未来』\}$

$\text{-Moonlight Sorcery-}\backslash Huge\; \backslash text\{-Moonlight\; Sorcery-\}$

$\text{『此时此刻的光辉』}\backslash Huge\; \backslash text\{『此时此刻的光辉』\}$

$\text{-My Happiness-}\backslash Huge\; \backslash text\{-My\; Happiness-\}$

$\text{『盼君勿忘』}\backslash Huge\; \backslash text\{『盼君勿忘』\}$

$\text{-Evidence of Existance-}\backslash Huge\; \backslash text\{-Evidence\; of\; Existance-\}$

$\text{『世界上最幸福的女孩』}\backslash Huge\; \backslash text\{『世界上最幸福的女孩』\}$

$\text{-Chtholly-}\backslash Huge\; \backslash text\{-Chtholly-\}$