题目
像素有点低啊~
算了凑合一下就好啦~
题目大意
给你一个首尾相接的数列，每次对一个区间进行操作：
顺时针操作，如果当前值比大，就交换。输出最后的。
比赛思路
首先这题的时限这么仁慈，一定有天大玄机。
并且一看这题，就感觉像是一个数据结构。
首先在想链表，但显然这题链表不可做。
然后一直在想带修主席树。
没想出来……
最后弃疗，直接打了个暴力。
WTF？15分？说好的25分呢？
然而实际上这题很没良心地捆绑数据，将10分和另外15分绑在一起了。
出题人，你怎么能这样子啊？你忍心吗？
正解
这题WMY大佬说可以用带修主席树做。
刚了一个下午，最终，他弃疗了……
原因是标记不好下传。
实际上正解是分块。
首先看到时间复杂度，我们就应该想到这题可以随意给你搞事情。
然而我就是没有想到分块！！！
首先，对于一个区间，如果有一个操作经过了这个区间，设区间中的最大值为。若，则交换，否则继续。
这个结论是很显然的，依靠这个结论可以再拿15分。
我们可以将其分块，每个块的大小为。对于每个块，我们维护一个大根堆，存下这个块里面的所有值。
如果处理整块，就直接和最大值比较，然后像之前一样操作。并且，在这个块上打一个标记。
如果处理散块，就要将这个散块还原，然后暴力搞一遍。
如何还原呢？
首先，对于每个块，我们将标记存在一个小根堆里面。
在还原的时候，我们从左到右扫，对于每个值，用小根堆的堆顶操作。如果，就交换（也就是将弹出，将加入，并且改变的值）
最后将标记清空。
这就还原了整个块了，然后暴力搞一遍，重构大根堆。
那么问题来了，为什么每次用小根堆的堆顶操作？
可以感性地理解一下：
对于第一个，这些标记的操作都会对它有操作。如果当前的这个值大于，那么就要被交换。而交换那么多遍，最后真正能对它做出影响的是最小的，其它的东西都会传到后面去。
然后对于后面的，也是一样的道理。
和氧化还原反应好像啊！——ZJQ
所以整块的时间复杂度是，散块的时间复杂度是
然后平衡规划一下，得出大概为。
然而分块的常数是有差异的，所以的取值据实际而定。
我取了。当我取时，程序就崩了，或许是堆太多了吧。（我用了STL的堆）
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 400000
#define K 800
int n,q;
int a[N];
int m;
#define bel(x) ((x)/K)
#define nxt(x) (((x)+1==m)?(0):((x)+1))
priority_queue<int> h[N/K];
priority_queue<int,vector<int>,greater<int> > bz[N/K];
inline void pushdown(int b,int l,int r,int &v){//处理散块
//还原
if (!bz[b].empty()){
for (int i=b*K;i<b*K+K && i<n;++i){
int t=bz[b].top();
if (a[i]>t){
bz[b].pop();
bz[b].push(a[i]);
a[i]=t;
}
}
while (!bz[b].empty())
bz[b].pop();
}
//暴力处理
for (int i=l;i<=r;++i)
if (a[i]>v)
swap(a[i],v);
//重构
while (!h[b].empty())
h[b].pop();
for (int i=b*K;i<b*K+K && i<n;++i)
h[b].push(a[i]);
}
inline void getinto(int b,int &v){//表示处理整块，v进入b中，再出来
int t=h[b].top();
if (t>v){
h[b].pop();
h[b].push(v);
bz[b].push(v);
v=t;
}
}
int main(){
scanf("%d%d",&n,&q);
for (int i=0;i<n;++i)
scanf("%d",&a[i]);
m=(n-1)/K+1;
for (int i=0;i<m;++i)
for (int j=0;j<K && i*K+j<n;++j)
h[i].push(a[i*K+j]);
while (q--){
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
l--,r--;
int bl=bel(l),br=bel(r);
if (bl==br){
if (l<=r)
pushdown(bl,l,r,v);
else{
pushdown(bl,l,min(bl*K+K-1,n-1),v);
for (int i=nxt(bl);i!=br;i=nxt(i))
getinto(i,v);
pushdown(br,br*K,r,v);
}
}
else{
if (l==bl*K)
getinto(bl,v);
else
pushdown(bl,l,min(bl*K+K-1,n-1),v);
for (int i=nxt(bl);i!=br;i=nxt(i))
getinto(i,v);
if (r==min(br*K+K-1,n-1))
getinto(br,v);
else
pushdown(br,br*K,r,v);
}
printf("%d
",v);
}
return 0;
}
我才发现原来要打个cpp才能有颜色，我之前打的都是C++，天哪，博客更新之后就是不一样！
总结
看见时限大的题，往分块方面想一想，或许就能很好解决了。
分块的优点，在于它只需要对整块和散块分块处理，也就是说，不像线段树那样下传时这么复杂。
还有，这题有没有其他的方法。比如，分块套分块（手动滑稽）