[Comet OJ Contest 14][ODT+树状数组]D.转转的数据结构题

上周打了Comet OJ 的比赛，质量很高…然而我在D题就被卡住了…
可能是从来没见过D这样的套路吧…我反而觉得E还要简单一些（然而细节真多qwq）

题面

题目描述

转转有一个长度为 $m$ 的整数序列 $c$，初值全是 $0$。

转转还有一个长度为 $n$ 的操作序列，第 $i$ 个操作用三元组 $(l_i,r_i,v_i)$ 描述，第 $i$ 个操作代表将 $c[l_i]?c[r_i]$ 赋值为 $v_i$ 。

现在，有 $q$ 个询问，第 $i$ 个询问有两个参数 $x_i$ , $y_i$ ($x_i\le y_i$)。

第 $i$ 次询问请你回答依序执行第 $x_i$ 到 $y_i$? 这 $y_i?x_i+1$ 个操作后，$c$ 序列中所有整数的和。每次询问开始时 $c$ 的所有数初值都会变回 $0$。

输入描述

第一行三个正整数 $n,m,q$，分别代表操作序列的长度、整数序列的长度以及询问的个数。

接下来还有 $n$ 行，当中的第 $i$ 行有 $3$ 个正整数 $l_i$ ,$r_i$ ,$v_i$，代表第 $i$ 个询问。

最后还有 $q$ 行，当中的第 $i$ 行有 $2$ 个正整数 $x_i,y_i$，表示第 $i$ 次询问。

输出描述

输出共 $q$ 行，每行一个整数， 第 $i$ 行的整数表示第 $i$ 次询问的答案。

样例输入 1

4 5 3
1 4 3
2 3 1
5 5 2
1 2 4
1 2
1 4
2 3

样例输出 1

8
14
4

样例输入 2

10 10 10
1 5 20
5 7 7
3 6 8
1 6 20
1 7 14
5 6 5
9 9 18
5 10 5
1 9 6
1 5 19
1 10
5 5
7 10
4 8
1 9
1 6
6 7
7 10
2 6
1 4

样例输出 2

124
98
124
86
59
80
28
124
80
1278
14
4

题解

听大佬说这是一道套路题…可能是我太菜了并不知道吧…
做这道题目之前，我们需要学习一个新的乱搞数据结构ODT(Old Driver tree-珂朵莉树)（没学过的百度一下就知道了，不过也可以看懂下面的文字）。
ODT擅长解决连续段修改的问题，符合ODT的应用范围。
其实ODT并不是什么新的数据结构，它只是用STL本身就有的set来支持一些新的操作。
具体来说，我们把数列上是同一操作修改的区间$[l,r]$计为三元组$(l,r,val)$。
对于一次修改$(l,r,val)$，我们把两边完整的三元组拆成两个（从$l$，$r$划分开），然后将原来包含在修改区间的三元组全部删去即可。
这样，我们就离线完成了$[1,p]$操作后的权值。
那么如何处理在区间$[q,p]$的查询呢？
我们可以将其看为在$q?p$时间内修改的权值和，然后将询问挂在$p$点上。那么我们只要在$p$时刻用树状数组记录在哪一时刻修改的权值，查询的时候查询从$q$开始的后缀和就好了。
由于我们每次最多增加两个区间，一个区间（拆开的算两个）只会删掉一次，因此操作数是$O(n)$的，因此时间复杂度是$O(n\log n)$。
那为什么其他的一些数据结构无法完成这道题目呢，其实这道题就相当于在对区间同色段修改做提出了可持久化的问题。一些数据结构由于本身特征可持久化后会浪费很多空间。
例如分块，在本题里只能够在每块都开以个$cnt$数组在时间$O(n\sqrt{n}\log n)$，空间$O(n\sqrt{n})$内完成，莫队的空间复杂度更为优秀，但时间复杂度同样无法接受。
至于线段树…其实线段树套树状数组也是可以通过这道题目的…只不过不并不好想…感兴趣的同学可以研究研究…（这东西是$O(n{\log }^{2}n)$的，不过跑起来和速度极慢的set差不多…）。
如果真的强制在线的话，或许可支持区间修改持久化线段树也能做?然而我并不是很会233…

实现

 /*Lower_Rating*/
/*comet 14 data_struct*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;#define LL long long
#define MAXN 500000
#define itr iterator
#define st set<node>int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*f;
}int n,m,Q;
LL ans[MAXN+5];
struct opt{
    int l,r,val;
}a[MAXN+5];
struct query{
    int l,r,id;
}q[MAXN+5];
struct Fenwick_tree{
    LL sum[MAXN+5];int lowbit(int x){
    return x&(-x);}void add(int x,LL y){
    if(x==0)return ;//****while(x<=n)sum[x]+=y,x+=lowbit(x);}LL Query(int x){
    LL res=0;while(x>0)res+=sum[x],x-=lowbit(x);return res;}
}T;
struct ODT{
    struct node{
    int l,r,val,id;bool operator <(const node &b)const{
    return r<b.r;}};st s;void init(){
    s.insert((node){
    1,m,0,0});}void split(st::itr x,int pos){
    int l=x->l,r=x->r,val=x->val,id=x->id;if(pos<l||pos>=r)return ;s.erase(x);s.insert((node){
    l,pos,val,id});s.insert((node){
    pos+1,r,val,id});}void Assign(int l,int r,int val,int id){
    st::itr x=s.lower_bound((node){
    0,l-1,0,0});split(x,l-1);st::itr y=s.lower_bound((node){
    0,r,0,0});split(y,r);x=s.lower_bound((node){
    0,l,0,0});y=s.lower_bound((node){
    0,r+1,0,0});for(st::itr i=x;i!=y;){
    st::itr j=i;i++;T.add(j->id,-1LL*((j->r)-(j->l)+1)*(j->val));s.erase(j);}s.insert((node){
    l,r,val,id});T.add(id,1LL*(r-l+1)*val);}
}D;
bool cmp(query s1,query s2){
    return s1.r<s2.r;
}int main(){
    n=read(),m=read(),Q=read();for(int i=1;i<=n;i++)a[i]=(opt){
    read(),read(),read()};for(int i=1;i<=Q;i++)q[i]=(query){
    read(),read(),i};sort(q+1,q+Q+1,cmp);D.init();for(int i=1;i<=Q;i++){
    for(int j=q[i-1].r+1;j<=q[i].r;j++)D.Assign(a[j].l,a[j].r,a[j].val,j);ans[q[i].id]=T.Query(n)-T.Query(q[i].l-1);}for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}