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

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

题面

题目描述

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

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

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

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

输入描述

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

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

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

输出描述

输出共 $q$q 行，每行一个整数， 第 $i$i 行的整数表示第 $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]计为三元组$(l,r,val)$(l,r,val)。
对于一次修改$(l,r,val)$(l,r,val)，我们把两边完整的三元组拆成两个（从$l$l，$r$r划分开），然后将原来包含在修改区间的三元组全部删去即可。
这样，我们就离线完成了$[1,p]$[1,p]操作后的权值。
那么如何处理在区间$[q,p]$[q,p]的查询呢？
我们可以将其看为在$q-p$q−p时间内修改的权值和，然后将询问挂在$p$p点上。那么我们只要在$p$p时刻用树状数组记录在哪一时刻修改的权值，查询的时候查询从$q$q开始的后缀和就好了。
由于我们每次最多增加两个区间，一个区间（拆开的算两个）只会删掉一次，因此操作数是$O(n)$O(n)的，因此时间复杂度是$O(n\log n)$O(nlogn)。
那为什么其他的一些数据结构无法完成这道题目呢，其实这道题就相当于在对区间同色段修改做提出了可持久化的问题。一些数据结构由于本身特征可持久化后会浪费很多空间。
例如分块，在本题里只能够在每块都开以个$cnt$cnt数组在时间$O(n\sqrt{n}\log n)$O(nn​logn)，空间$O(n\sqrt{n})$O(nn​)内完成，莫队的空间复杂度更为优秀，但时间复杂度同样无法接受。
至于线段树…其实线段树套树状数组也是可以通过这道题目的…只不过不并不好想…感兴趣的同学可以研究研究…（这东西是$O(n\log^2 n)$O(nlog2n)的，不过跑起来和速度极慢的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]);
}