牛客练习赛-91 BC

题目

题意: 给定n个可见的ASCII字符(33-126)，有m次询问,字符c,[l,r]。每次询问代表，可以将所在区间的字符换成该字符无限次。也就是说，对于[l,r]所覆盖的区间，可以取到最大的一个字符c.问发生任意次替换后，n个字符的和最大是多少。(可能说的不是很清楚，题目说的很清楚)  简单版:n = 1e5,m = 1e5  困难版:n = 1e7,m = 1e6 思路: 简单版，我直接写的线段树维护区间最大值。O(mlogn). 题解说的差分写，O(94 * n)，学到了。对于每个字符，记录下它拥有的区间。对于区间[l,r],转化为a[l]++,a[r+1]–.维护前i个数的和now,如果now> 0,说明可以进行字符的替换。 对于每个字符，都跑一遍差分。 重点是困难版怎么做，n是1e7，要用线性做法。 答案是用并查集加速差分做法的遍历，让所有元素最多被遍历到一次，就可以达到O(n * α(n)).按照字符从大到小排序，大的字符覆盖过的点就不需要用小的字符来覆盖了。 对于当前遍历的点i，不再使用i++，而是i = find(i)，并且把i合并到它右侧的并查集中，fa[i] = find(i+1)，因为它应该向右走一个单位，但是i+1可能访问过了，改为直接指到它所在并查集的祖节点。 这个做法还在今晚的atcoder做了一个题，学海无涯，回头是岸。

代码: 简单版:

// Problem: 魔法学院(easy version)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11181/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>n>>m;
     for(int i=1;i>ch;
     	a[i] = ch;
     }
     while(m--)
     {
     	int l,r; char ch; cin>>l>>r>>ch; int x = ch;
     	va[x].push_back({l,r});
     }
     for(int k=126;k>=33;--k)
     {
     	if(!va[k].size()) continue;
     	for(int j=0;jm;
     for(int i=1;i>ch;
     	a[i] = ch;
     	fa[i] = i;
     }
     fa[n+1] = n+1;
     while(m--)
     {
     	int l,r; char ch; cin>>l>>r>>ch; int x = ch;
     	va[x].push_back({l,r});
     }
     for(int k=126;k>=33;--k)
     {
     	for(int i=0;i