目录

[luogu P4230]连环病原体

迁移提示
本文迁移自博客园, 原文链接

[luogu P4230] 连环病原体

题意

给定一个长度为 $n$ 的边序列, 当这个序列的一个子区间内的边都加入图中时产生了环则称其为"加强区间", 求序列中的每条边在多少个加强区间中.

$n\le 4\times 10^5,|V|\le 2\times 10^5$.

题解

想打休闲板子于是想起了这道上古XCR题…XCR #12好像要咕?

首先有一个显然的沙雕性质: 如果一个子区间是加强区间, 那么所有包含这个子区间的区间也是加强区间.

接着我们按照套路, 求所有以 $i$ 为右端点的加强区间对答案产生的贡献. 这部分需要快速求.

根据上面的沙雕性质, 我们只要求出以 $i$ 为右端点的最短加强区间的左端点 $l$, 那么所有小于 $l$ 的左端点也是加强区间. 于是对于所有坐标为 $k$ 且 $k<l$ 的位置都会产生 $k$ 的贡献, 而对 $k\in [l,i]$ 则会产生 $l$ 的贡献. 于是就变成了区间加等差数列单点求值, 随手拉个线段树就可以搞了.

问题变成怎么求最短加强区间. 不难发现因为有上面的沙雕单调性直接双指针就可以了. 但是加边/删边是随机的, 所以只能用LCT维护.

跑得巨快无比. 虽然数据范围有 $2\times 10^5$ 个点但是我的常数大如狗的LCT板子极限数据才跑了 $300\texttt{ms}$…

记得当时毒瘤oscar造数据的时候专门卡了查完根不Splay的选手233333

参考代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <bits/stdc++.h>

const int MAXN=4e5+10;
typedef long long intEx;

struct LCT{
#define lch chd[0]
#define rch chd[1]
#define kch chd[k]
#define xch chd[k^1]
    struct Node{
        bool rev;
        Node* prt;
        Node* pprt;
        Node* chd[2];
        Node():rev(false),prt(NULL),pprt(NULL),chd{NULL,NULL}{}
        void Flip(){
            if(this!=NULL){
                this->rev=!this->rev;
                std::swap(this->lch,this->rch);
            }
        }
        void PushDown(){
            if(this!=NULL&&this->rev){
                this->lch->Flip();
                this->rch->Flip();
                this->rev=false;
            }
        }
    };
    std::vector<Node*> N;
    LCT(int n):N(n+1){
        for(int i=1;i<=n;i++)
            N[i]=new Node();
    }
    void Rotate(Node* root,int k){
        Node* tmp=root->xch;
        root->PushDown();
        tmp->PushDown();
        tmp->prt=root->prt;
        if(root->prt==NULL){
            tmp->pprt=root->pprt;
            root->pprt=NULL;
        }
        else if(root->prt->lch==root)
            root->prt->lch=tmp;
        else
            root->prt->rch=tmp;
        root->xch=tmp->kch;
        if(root->xch!=NULL)
            root->xch->prt=root;
        tmp->kch=root;
        root->prt=tmp;
    }
    void Splay(Node* root){
        while(root->prt!=NULL){
            int k=root->prt->lch==root;
            if(root->prt->prt==NULL)
                Rotate(root->prt,k);
            else{
                int d=root->prt->prt->lch==root->prt;
                Rotate(k==d?root->prt->prt:root->prt,k);
                Rotate(root->prt,d);
            }
        }
    }
    void Expose(Node* root){
        Splay(root);
        root->PushDown();
        if(root->rch){
            root->rch->pprt=root;
            root->rch->prt=NULL;
            root->rch=NULL;
        }
    }
    bool Splice(Node* root){
        Splay(root);
        if(root->pprt==NULL)
            return false;
        Expose(root->pprt);
        root->pprt->rch=root;
        root->prt=root->pprt;
        root->pprt=NULL;
        return true;
    }
    void Access(Node* root){
        Expose(root);
        while(Splice(root));
    }
    void Evert(Node* root){
        Access(root);
        root->Flip();
    }
    void Link(int a,int b){
        Node* x=N[a];
        Node* y=N[b];
        Evert(y);
        y->pprt=x;
    }
    void Cut(int a,int b){
        Node* x=N[a];
        Node* y=N[b];
        Evert(x);
        Access(y);
        y->PushDown();
        y->lch->prt=NULL;
        y->lch=NULL;
    }
    Node* FindRoot(int x){
        Node* cur=N[x];
        Access(cur);
        while(cur->lch)
            cur=cur->lch;
        Splay(cur);
        return cur;
    }
#undef lch
#undef rch
#undef xch
#undef kch
};

struct Node{
    int l;
    int r;
    intEx add;
    intEx delta;
    Node* lch;
    Node* rch;
    Node(int,int);
    void PushDown();
    intEx Query(int);
    void Add(intEx,intEx);
    void Add(int,int,intEx,intEx);
};

int n;
int v;
std::pair<int,int> E[MAXN];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&E[i].first,&E[i].second);
        v=std::max(E[i].first,v);
        v=std::max(E[i].second,v);
    }
    Node* N=new Node(1,n);
    LCT* T=new LCT(v);
    int l=0;
    for(int i=1;i<=n;i++){
        while(T->FindRoot(E[i].first)==T->FindRoot(E[i].second)){
            ++l;
            T->Cut(E[l].first,E[l].second);
        }
        T->Link(E[i].first,E[i].second);
        if(l!=0){
            N->Add(l+1,i,l,0);
            N->Add(1,l,1,1);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld%c",N->Query(i)," \n"[i==n]);
    return 0;
}

inline void Node::PushDown(){
    if(this->add!=0||this->delta!=0){
        this->lch->Add(this->add,this->delta);
        this->rch->Add(this->add+this->delta*(this->rch->l-this->l),this->delta);
        this->add=this->delta=0;
    }
}

inline void Node::Add(intEx a,intEx d){
    if(this!=NULL){
        this->add+=a;
        this->delta+=d;
    }
}

intEx Node::Query(int x){
    if(this->l==this->r)
        return this->add;
    else{
        this->PushDown();
        if(x<=this->lch->r)
            return this->lch->Query(x);
        else
            return this->rch->Query(x);
    }
}

void Node::Add(int l,int r,intEx a,intEx d){
    if(l<=this->l&&this->r<=r)
        this->Add(a+(this->l-l)*d,d);
    else{
        this->PushDown();
        if(l<=this->lch->r)
            this->lch->Add(l,r,a,d);
        if(this->rch->l<=r)
            this->rch->Add(l,r,a,d);
    }
}

Node::Node(int l,int r):l(l),r(r),add(0),delta(0),lch(NULL),rch(NULL){
    if(l!=r){
        int mid=(l+r)>>1;
        this->lch=new Node(l,mid);
        this->rch=new Node(mid+1,r);
    }
}

https://pic.rvalue.moe/2021/08/02/54d3241c9ebf3.png