珂朵莉树

珂朵莉树可以较快地实现：

区间加
区间赋值
求区间第k大值
求区间n次方和

珂朵莉树的思想在于随机数据下的区间赋值操作很可能让大量元素变为同一个数。所以我们以三元组<l,r,v>的形式保存数据（区间[l,r]中的元素的值就是v）：

代码为：

struct node
{
    ll l, r;
    mutable ll v; // 这里mutable要写不然可能会CE
    node(ll l, ll r, ll v) : l(l), r(r), v(v) {} // 构造函数
    bool operator<(const node &o) const { return l < o.l; } // 重载小于运算符
};

需要一个数据结构进行存储以及修改

set是个不错的选择

把这些三元组存储到 set 里

1	set<node> tree;

有一个细节点，就是需要内部重载小于运算符号。

set会保证内部元素有序（插入、删除和查询的时间复杂度都是 O(log⁡n) ）。而mutable使得当整个结构体为const时，标为mutable的成员仍可变（因为可能有区间加等操作）。

我们进行区间操作时并不总是那么幸运，可能会把原本连续的区间断开。我们需要一个函数来实现“断开”的操作，把<l,r,v>断成<l,pos-1,v>和<pos,r,v>：

这也正是核心操作

实际很简单，一个集合中，有一部分需要修改，而另一部分不需要修改，就把集合拆开，拆成两部分。（要修改的就修改，不修改的就算了

auto split(ll pos)
// 若不支持C++14，auto须改为set<node>::iterator
{
    auto it = tree.lower_bound(node(pos, 0, 0)); // 寻找左端点大于等于pos的第一个节点
    // 若不支持C++11，auto须改为set<node>::iterator
    if (it != tree.end() && it->l == pos) // 如果已经存在以pos为左端点的节点，直接返回
        return it;
    it--; // 否则往前数一个节点
    ll l = it->l, r = it->r, v = it->v;
    tree.erase(it); // 删除该节点
    tree.insert(node(l, pos - 1, v)); // 插入<l,pos-1,v>和<pos,r,v>
    return tree.insert(node(pos, r, v)).first; // 返回以pos开头的那个节点的迭代器
                                               // insert默认返回值是一个pair，第一个成员是我们要的
}

区间赋值

void assign(ll l, ll r, ll v)
{
    auto end = split(r + 1), begin = split(l); // 顺序不能颠倒，否则可能RE
    tree.erase(begin, end); // 清除一系列节点
    tree.insert(node(l, r, v)); // 插入新的节点
}

其他操作

区间加

void add(int l, int r, LL val)
{
    IT itl = split(l),itr = split(r+1);
    for (; itl != itr; ++itl) 
        itl->v += val;
}

求区间k大值（直接扔到vector里排下序）：

ll kth(ll l, ll r, ll k)
{
    auto end = split(r + 1);
    vector<pair<ll, ll>> v; // 这个pair里存节点的值和区间长度
    for (auto it = split(l); it != end; it++)
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
    for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
    {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
}

求区间n次方和（用快速幂直接求）：

ll sum_of_pow(ll l, ll r, ll x, ll y)
{
    ll tot = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y; // qpow自己写一下
    return tot;
}

Physical Education Lessons

题面翻译

题意：

Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！

Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：

从现在到学期结束还有 $n$ 天(从 $1$ 到 $n$ 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 $q$ 个指令，每个指令可以用三个参数 $l,r,k$ 描述：

如果 $k=1$，那么从 $l$ 到 $r$ （包含端点）的所有日子都变成非工作日。
如果 $k=2$，那么从 $l$ 到 $r$ （包含端点）的所有日子都变成工作日。

帮助Alex统计每个指令下发后，剩余的工作日天数。

输入格式：

第一行一个整数 $n$，第二行一个整数 $q$ $(1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)$，分别是剩余的天数和指令的个数。

接下来 $q$ 行，第 $i$ 行有 $3$ 个整数 $l_i,r_i,k_i$，描述第 $i$ 个指令 $(1\le l_i,r_i\le n,\;1\le k\le 2)$。

输出格式：

输出 $q$ 行，第 $i$ 行表示第 $i$ 个指令被下发后剩余的工作日天数。

Translated by 小粉兔

题目描述

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are $ n $ days left before the end of the term (numbered from $ 1 $ to $ n $ ), and initially all of them are working days. Then the university staff sequentially publishes $ q $ orders, one after another. Each order is characterised by three numbers $ l $ , $ r $ and $ k $ :

If $ k=1 $ , then all days from $ l $ to $ r $ (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;
If $ k=2 $ , then all days from $ l $ to $ r $ (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days.

Help Alex to determine the number of working days left after each order!

输入格式

The first line contains one integer $ n $ , and the second line — one integer $ q $ ( $ 1<=n<=10^{9} $ , $ 1<=q<=3·10^{5} $ ) — the number of days left before the end of the term, and the number of orders, respectively.

Then $ q $ lines follow, $ i $ -th line containing three integers $ l_{i} $ , $ r_{i} $ and $ k_{i} $ representing $ i $ -th order ( $ 1<=l_{i}<=r_{i}<=n $ , $ 1<=k_{i}<=2 $ ).

输出格式

Print $ q $ integers. $ i $ -th of them must be equal to the number of working days left until the end of the term after the first $ i $ orders are published.

样例 #1

样例输入 #1

样例输出 #1

#include <bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
struct node
{
    int l,r;
    mutable bool v;
    node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};
set<node> s;
int sum=0;
IT split(int pos)
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) 
        return it;
    --it;
    int L = it->l, R = it->r;
    bool V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
}
void assign_val(int l,int r,bool val)
{
    IT itr = split(r+1), itl = split(l), it = itl;
    for( ;itl != itr; ++itl)
        sum-=itl->v*(itl->r-itl->l+1); //过程中顺带计算
    s.erase(it,itr);
    s.insert(node(l,r,val));
    sum+=val*(r-l+1); //过程中顺带计算
}
int main()
{
     ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n,m;
    cin>>n>>m;
	s.insert(node(1,n,1));
	sum=n;
	while(m--)
	{
	int l,r,op;
        cin>>l>>r>>op;
		if(op==1) //修改
			assign_val(l,r,0);
		else
			assign_val(l,r,1);
		cout<<sum<<'\n';
	}
}