我永远喜欢珂朵莉树

fkxr · 2025-07-12 09:57:35 · 题解

纪念第一次不看题解做出我们省的题。

从前往后维护每个操作的贡献，每次查询把区间贡献加起来。用珂朵莉树维护每个操作，具体记录每段区间和值的同时维护这是第几个操作的区间，然后这个操作区间被覆盖的时候把它的贡献减掉被覆盖的那部分就行了。

你写着写着就会发现问题，每次查询 r 时，后面的区间这次没有执行，但它们会把现在查询区间的贡献覆盖掉，我们希望查询的 r 从小到大排列，所以离线之后在 r 上挂扫描线，就过了。

时间复杂度

珂朵莉树：O(n\log m)。
单点修改贡献（因为历史总段数是 O(n) 的，所以只会修改 O(n) 次，这里使用树状数组）：O(n\log n)。
区间查询贡献和：O(m\log n)。

总时间复杂度：可过。

Code


// @author       fkxr(luogu uid = 995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
#define int long long
#define _CRT_SECURE_NO_WARNINGS 1
#define _4x _4x
#define BIT BIT
//#define ST ST
//#define dsu dsu
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

define ds(x) (x=='\r'||x=='\n'||x==' ')

define MAX 20

namespace fastIO { template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; } template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); } struct FIstream { inline FIstream operator>>(int& a) { r(a); return{}; } inline FIstream operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; } inline FIstream operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; } template<typename T>inline FIstream operator<<(T& a) { r(a); return{}; } inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } } }in; struct FOstream { inline FOstream operator<<(const int a) { w(a); return{}; } inline FOstream operator<<(const char ch) { pc(ch); return{}; } inline FOstream operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; } template<typename T>inline FOstream operator>>(const T a) { w(a); return{}; } }out; }using fastIO::in; using fastIO::out;

undef ds

define eout cerr

namespace Maths { const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 }; inline bool IP1(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }

define times(a,b,m) (c=(unsigned long long)ab-(unsigned long long)((long double)a/mb+0.5L)*m,c<m?c:m+c)

inline int power(int a, int b, const int mod = -1) { unsigned long long c; int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = times(ans, a, mod); b >>= 1; a = times(a, a, mod); }return ans; }
const int Suk[] = { 2,325,9375,28178,450775,9780504,1795265022 };
inline bool chk(const int n, int a, int b, int x) { if (x >= n) return 1; unsigned long long c; int v = power(x, a, n); if (v == 1)return 1; int j = 1; while (j <= b) { if (v == n - 1)break; v = times(v, v, n); j++; }if (j > b)return 0; return 1; }
inline bool IP(int n) { if (n < 3 || n % 2 == 0)return n == 2; if (n <= 1e6) { return IP1(n); } else { int a = n - 1, b = 0; while (a % 2 == 0)a >>= 1, b++; for (int k : Suk)if (!chk(n, a, b, k))return 0; return 1; } }

undef times

} using Maths::power; using Maths::IP; namespace exs {

ifdef _4x

int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };

else

int dx[] = { 1,0,-1,-1,1,1,0,-1 }, dy[] = { 1,1,1,0,0,-1,-1,-1 };

endif

template<typename T, typename T1, typename T2>inline bool rg(T l, T1 r, T2 x) { return l <= x && x <= r; }
inline bool emc(const int& a, const int& b) { return a > b; }
void Freopen(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}

ifdef BIT

struct bit {
    vector<int> c0, c1; int n;
    inline void Add(vector<int>& c, int p, int v) { for (; p <= n; p += p & -p) c[p] += v; }
    inline int Sum(const vector<int>& c, int p) { int t = 0; for (; p; p -= p & -p) t += c[p]; return t; }
    inline int sum(int l, int r) { assert(n != 0); return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
    inline void add(int l, int r, int v) { assert(n != 0); Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
    inline void init(const vector<int>& c) { n = c.size() - 1; c0.resize(n + 2); c1.resize(n + 2); int last = 0; for (int i = 1; i <= n; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
};

endif

ifdef ST

struct st {
    vector<int> lg; vector<vector<int>> f;
    inline void init(const vector<int>& c) { int len = c.size() - 1; lg.resize(len + 2); for (int i = 2; i <= len; i++) lg[i] = lg[i >> 1] + 1; f.resize(18, vector<int>(len + 2)); for (int i = 1; i <= len; i++) f[0][i] = c[i]; for (int j = 1; (1 << j) <= len; j++) for (int i = 1; i + (1 << j) - 1 <= len; i++) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]); }
    inline int q(int l, int r) { int j = lg[r - l + 1]; return max(f[j][l], f[j][r - (1 << j) + 1]); }
};

endif

ifdef dsu//0x

struct dsu {
    vector<int> fa, size; dsu(int size_) :fa(size_), size(size_, 1) { iota(fa.begin(), fa.end(), 0); }
    inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    inline void unite(int x, int y) { x = find(x), y = find(y); if (x == y)return; if (size[x] < size[y])swap(x, y); fa[y] = x; size[x] += size[y]; }
};

endif

}using namespace exs; struct node{ int l,r,v,t; node(int L=0,int R=0,int V=0,int T=0){l=L,r=R,v=V,t=T;} inline friend bool operator<(node a,node b){return a.l<b.l;} };node e[500005]; set<node>s;

define auto set<node>::iterator

bit tr;//数状数组 auto split(int x){ auto it=s.lower_bound(node(x,0,0)); if(it!=s.end()&&it->l==x)return it; --it;node tmp=it;s.erase(it); s.insert(node(tmp.l,x-1,tmp.v,tmp.t)); return s.insert(node(x,tmp.r,tmp.v,tmp.t)).first; } void assign(int l,int r,int v,int t){ tr.add(t,t,(r-l+1)v);//加贡献 auto itr=split(r+1),it=split(l); for(;it!=itr;++it)tr.add(it->t,it->t,-(it->r-it->l+1)*it->v);//减掉被覆盖的操作的贡献 it=split(l);s.erase(it,itr); s.insert(node(l,r,v,t)); } vector<node>q[500005]; int ans[500005]; void Main() { int n,m,Q;in>>n>>m>>Q; tr.init(vector<int>(n+5,0)); s.insert(node(1,m,0,1)); for(int i=1;i<=n;i++){ in>>e[i].l>>e[i].r>>e[i].v; e[i].t=i; } for(int i=1;i<=Q;i++){ int l,r;in>>l>>r; q[r].push_back(node(l,r,i));//r上挂扫描线 } for(int i=1;i<=n;i++){ assign(e[i].l,e[i].r,e[i].v,e[i].t); for(node j:q[i])ans[j.v]=tr.sum(j.l,j.r); } for(int i=1;i<=Q;i++)out<<ans[i]<<'\n'; } signed main() { Main(); return 0; }


[记录](https://www.luogu.com.cn/record/223803826)