CSP-精练

目前考过了2次CSP，分别拿到了290和320分，感觉需要着重练习一下4、5题，在记录重点题目的练习前先谈谈我的感受。

（1）首先对于第一题，毫无疑问这100分一定是送的，就算你读完一遍题目没有头绪，也可以在提示中找到解题方法，不再过多阐述。
（2）对于第二题，这是一道比较吃基本算法的题，26次CSP认证考的是如何处理稀疏大数组，27次考的是类似于0-1背包的动态规划，对于有算法基础的人来说还是可以通过思考快速解决的，最好需要熟悉一些基本的诸如：归并、动态规划、贪心等算法。
（3）对于第三题，是一道不折不扣的大模拟，不太吃算法，基本上暴力模拟出来就能解决，如果你用cin和cout比较多的话，尽量使用下面这行代码进行优化：

ios::sync_with_stdio(0);

第三题一定要设计好数据结构，可以通过定义结构体或充分利用$~STL~$中的容器存储数据，理清逻辑还是可以暴力求解的。
（4）对于第四、五题：感觉这就很吃算法能力了，即需要利用合适的算法进行求解，还需要充分得进行优化，这也是我在这篇文章中所要着重练习的地方，如果没有多加练习很难进行突破，毕竟oi爷也都是经过大量练习才能随随便便CSP500的。

仅考过两次CSP，经验还不多，那么我们直接就从第27次CSP认证的4、5题上手吧！

[27-4] 吉祥物投票（vote）

【题目描述】

为了促进西西艾弗岛上的旅游业发展，当地决定设计一个吉祥物形象。活动吸引了众多设计领域的大师和爱好者参加，经过初步筛选，共选出了 m 个作品，编号为 1 ∼ m，进行最终的投票角逐。
活动还吸引了西西艾弗岛上的 n 名投票者参与，编号为 1 ∼ n，每人都在最终的投票环节拥有投一票的权利，也可以放弃投票。我们定义每个人的投票意愿 $~a_i(1 ≤ i ≤ n)~$为一个 0 ∼ m 的整数，若 $~a_i = 0~$ 表示这个人目前没有支持的作品，打算放弃投票，否则表示这个人支持第 $~a_i~$ 号作品并有意愿将票投给它。
最初，由于所有人对参与竞选的作品都不了解，因此投票意愿 $~a_i~$ 均为 0。接下来是紧张刺激的拉票环节，作品的设计者们要想方设法给自己的作品拉票，这一过程中可能出现如下若干种事件：
1 l r x：编号为 x 的作品开展了一场拉票活动，成功地吸引了编号为 l ∼ r 的投票者的兴趣，使得他们的投票意愿全部改为 x。
2 x w：编号为 x 的作品需要经历一次大规模修改，所以需要暂时退出竞选。由于x 与 w 两个作品的风格较为相近，因此原先投票意愿为 x 的投票者的投票意愿变为了w。特别地，若 w = 0，表示这些投票者暂时找不到新的支持的作品。需要注意的是，作品 x 退出竞选只是暂时的，因此后续的事件中作品 x 仍可能出现。
3 x y：主办方发现自己的统计出现了失误，将编号为 x 和 y 的作品弄颠倒了。发布勘误后，所有原先投票意愿为 x 的投票者的投票意愿变为了 y，所有原先投票意愿为y 的投票者的投票意愿变为了 x。
4 w：主办方决定进行一次调查：希望知道所有投票者中，当前投票意愿为 w 的有多少人。若 $~w\not=0~$ ，相当于调查有多少投票者目前支持作品 w ，否则相当于调查有多少投票者目前没有支持的作品。
5：主办方决定进行一次调查：若以现在的投票意愿进行最终的投票，获胜的作品是哪一个。规定得票数至少为 1 且最多的作品获胜，得票数相同则编号较小的作品获胜。特别地，若所有作品均无得票，认为不存在获胜作品。
从拉票开始到结束，共出现了 q 次如上的事件。由于参选的作品数和投票人数实在太多，单凭活动主办方的能力难以全面统计，现在请你编写一个程序来处理这些事件，并求出每次调查的结果。

【输入格式】

从标准输入读入数据。
第 1 行，3 个正整数 n, m, q。
接下来 q 行，每行 1 ∼ 4 个非负整数，描述一个事件。

【输出格式】

输出到标准输出。
对于每个 4 或 5 事件输出一行，一个非负整数表示此次调查的结果。
其中事件 5 若 不存在获胜作品则输出0。

【样例 1 输入】

10 2 15
5
1 2 4 1
1 4 7 2
4 1
5
1 3 4 1
5
1 7 9 1
3 1 2
4 2
2 1 2
4 2
2 2 0
4 2
5

【样例 1 输出】

0
2
2
1
6
8
0
0

【数据范围】

对于所有的数据，满足 $~1 ≤ n ≤ 10^9，1 ≤ m, q ≤ 10^5，1 ≤ l ≤ r ≤ n，1 ≤ x, y ≤ m，0 ≤ w ≤ m~$。
保证事件 2 中 x≠w，事件 3 中 x≠y。

【正解】

我们先来整理以下题目大意：
有$~m~$个作品（编号1-m），$~n~$个投票者（编号1-n），投票者就是一个长度为$~n~$的序列，初始值为0，需要支持下列操作：
①$~1~l~r~x~$：把区间$~[l,r]~$中的数据变为$~x~$
②$~2~x~w~$：把区间$~[1,n]~$值为$~x~$的数据替换为$~w~$
③$~3~x~y~$：交换区间$~[1,n]~$中值分别为$~x~$和$~y~$的数据
④$~4~w~$：统计区间$~[1,n]~$中值为$~w~$的数据个数
⑤$~5~$：统计区间$~[1,n]~$中出现次数最多的数据
序列长度$~n\le10^9~$，参赛作品数$~m\le10^5~$，操作个数$~q\le10^5~$

显然，如果想要拿满分，开大数组是不可能的；但是如果想要拿部分分，直接开数组是最好的选择，按照题目要求暴力循环各个操作就可以拿到20分（我不会告诉你这个人就是我）。
既然数组开不到$~10^9~$，那么我们该怎么办呢？因为注意到测试集中有特殊的只有1、4、5事件的，所以首先从1操作入手，注意到1操作是分段的操作，因此我们可以利用一个比较玄学的东西：颜色段均摊

颜色段均摊

颜色段均摊算法也叫做珂朵莉树，亦可简称ODT（Old Driver Tree），至于为什么叫这个名字，可以看看它的来源CF896C Willem, Chtholly and Seniorious，我们在下文将其简称为ODT，这是一个暴力玄学的基于 std::set 数据结构，对于随机的数据非常有效。

有一类问题，对一个序列，进行一个区间推平操作。就是把一个范围内，比如 [ l , r ] 范围内的数字变成同一个。除了推平之外，也可能夹杂着其它操作。如果数据是随机的，就可以用ODT，我们可以将具有相同值的一段数据区间看作一个结点，结点定义如下：

struct node{
    int l,r;//结点对应的左右端点
    mutable int v;//结点值，加上mutable是为了在set中能对v进行修改
    node(int L,int R=0,int V=0):l(L),r(R),v(V){}//构造函数
    friend bool operator < (node a,node b){return a.l<b.l;}//重载<，在set中按照结点左端点大小进行排序
};

ODT的核心操作是 split，这是因为后续操作中有的node一部分需要修改，而另一部分不需要修改，为此我们需要进行切分。

set<node> s;
set<node>::iterator split(int pos){
    set<node>::iterator it=s.lower_bound(node(pos));//找到s中第一个l不小于pos的node
    if(it!=s.end() && it->l==pos)//找到了node并且pos就是它的左边界l,直接返回it
        return it;
    --it;//pos在上一个结点对应的区间中
    if(it->r < pos) return s.end();//特殊情况，未找到合适的node，返回s.end()
    int L=it->l,R=it->r;
    int V=it->v;
    //将it对应的结点替换为[l,pos-1]和[pos,r]两个结点，实现切分
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;//first返回的是新插入结点的迭代器，pos是它的左端点
}

比如对于上述图例，我们要执行一个操作：将 [ 2 , 8 ] 中的值替换为666，则需要先执行split操作以便替换方便：

值得注意的是：修改 [ l , r ] 区间中的值之前，对于set进行split操作时，需要先执行 split(r+1)，再执行 split(l)
实现完核心功能后，我们就可以定义一些相关操作了：

• 推平 assign：将$~[l,r]~$中的值改为x

inline void assign(int l,int r,int x){
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);//删除掉[itl,itr)
    s.insert(node(l,r,x));//插入新区间
}

看下图可以更直观得理解操作的原理：

• 增加 add：给$~[l,r]~$中的值加上x

inline void add(int l,int r,int x){
    set<node>::iterator itr=split(r+1),itl=split(l);
    for(;itl!=itr ; ++itl) itl->v += x; //遍历[itl,itr)加上x就行
}

还有其他的操作，因为本题用不上，就不再过多赘述了，利用ODT我们解决该题的操作1应该是没问题了，操作2、3不妨先暴力解决，对于操作4、5，每当执行该操作时遍历一遍ODT，更新记录得票数的 vector，1.0版本代码如下：

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

struct node{
    int l,r;//结点对应的左右端点
    mutable int v;//结点值，加上mutable是为了在set中能对v进行修改
    node(int L,int R=0,int V=0):l(L),r(R),v(V){}//构造函数
    friend bool operator < (node a,node b){return a.l<b.l;}//重载<，在set中按照结点左端点大小进行排序
};

set<node> s;//所要维护的ODT，记录投票情况 
vector<int> work;//作品获票数，下标1-m 
int n,m,q;//投票数，作品数，操作数

set<node>::iterator split(int pos){//颜色段切割 
    set<node>::iterator it=s.lower_bound(node(pos));//找到s中第一个l不小于pos的node
    if(it!=s.end() && it->l==pos)//找到了node并且pos就是它的左边界l,直接返回it
        return it;
    --it;//pos在上一个结点对应的区间中
    if(it->r < pos) return s.end();//特殊情况，未找到合适的node，返回s.end()
    int L=it->l,R=it->r;
    int V=it->v;
    //将it对应的结点替换为[l,pos-1]和[pos,r]两个结点，实现切分
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;//first返回的是新插入结点的迭代器，pos是它的左端点
}
inline void assign(int l,int r,int x){//将[l,r]替换为x 
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);//删除掉[itl,itr)
    s.insert(node(l,r,x));//插入新区间
}

inline void change(int x,int w){//将x改为w，暴力遍历实现，待修改 
	set<node>::iterator it;
	for(it=s.begin();it!=s.end();++it){//第一遍遍历修改值 
		if(it->v==x){
			it->v=w;
		}
	}
}

inline void swap(int x,int y){//将x改为y，将y改为x，暴力遍历实现，待修改 
	set<node>::iterator it;
	for(it=s.begin();it!=s.end();++it){//第一遍遍历修改值 
		if(it->v==x){
			it->v=y;
		}
		else if(it->v==y){
			it->v=x;
		}
	}
} 

inline void update(){//遍历s，更新work 
	for(int i=0;i<=m;++i){//初始化work 
		work[i]=0;
	} 
	set<node>::iterator it;
	for(it=s.begin();it!=s.end();++it){
		work[it->v]+=it->r-it->l+1;
	}
}

inline void merge(){
	set<node>::iterator it;
	for(it=s.begin();it!=--s.end();){//第二遍遍历合并具有相同值的相邻结点 
		set<node>::iterator it1=it;it1++;
		if(it1->v==it->v) {//相邻结点值相同，进行合并 
			int L=it->l,R=it1->r,V=it->v;
			set<node>::iterator it2=it1;it2++;
			s.erase(it,it2);
			it=s.insert(node(L,R,V)).first;
		}
		else{
			it++;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);//优化cin
	cin>>n>>m>>q;
	for(int i=0;i<=m;++i){//初始化作品投票数 
		work.push_back(0);
	}
	s.insert(node(1,n,0));//投票情况记录，初始化1-n投票都为0 
	for(int i=0;i<q;++i){//处理操作 
		int op;
		cin>>op;
		if(op==1){//执行1操作
			int l,r,x;
			cin>>l>>r>>x;
			assign(l,r,x);//[l,r]投票者投票给作品x
		}
		else if(op==2){//执行2操作 
			int x,w;
			cin>>x>>w;
			change(x,w);//x作品投票者转为给w投票 
		}
		else if(op==3){//执行3操作 
			int x,y;
			cin>>x>>y;
			swap(x,y);//交换x作品和y作品的投票情况 
		}
		else if(op==4){//执行4操作 
			int w;
			cin>>w;
			update();
			cout<<work[w]<<endl;//输出作品w的得票数 
		} 
		else if(op==5){//执行5操作 
			update();
			vector<int>::iterator it=max_element(work.begin()+1,work.end());//获取得票数最多的作品指针 
			if(*(it)==0) cout<<0<<endl;//无投票 
			else{
				int winer=it-work.begin();
				cout<<winer<<endl;
			} 
		} 
		merge();
//		set<node>::iterator it;
//		for(it=s.begin();it!=s.end();it++){
//			cout<<"("<<it->l<<","<<it->r<<","<<it->v<<")"<<endl;
//		}
	} 
	return 0;
} 

利用上述代码我们可以得到45分，比暴力开数组多了25分，说明我们的ODT较好得解决了操作1，但是操作2、3是暴力实现的，还需要进一步得对算法进行优化。