P5350 序列
2024-10-19 11:51:01
P5350 序列
题意
维护一个序列，支持区间求和、赋值、加值、复制、交换、翻转操作，其中交换和复制操作保证两段区间长度相等且不交。答案对 \(1e9+7\) 取模。
思路
对于区间求和、赋值、加值、交换、翻转操作我们都可以很轻松地使用平衡树进行维护。所以现在的难点就在于复制操作：如何复制一段区间？
如果我们暴力复制的话，每次我们不得不将被复制的子树扫一遍进行复制，这是肯定不行的。
于是我们使用可持久化平衡树。其中心思想就是每次修改一个节点的信息时，将该节点复制一遍。这样我们在进行复制操作的时候就可以复制出来一个新的树而不会对原树有影响，而且因为不是每次都遍历子树，所以时间复杂度正确。
但是因为要丢弃之前的节点所以空间复杂度略微有些大。因为我们可以进行垃圾回收定期重构使得空间被合理重复利用。
于是这道题就解决了。我使用了 FHQ treap 进行实现，因为发现对于这些操作 FHQ 会比较方便。
然后这道题不卡 ODT 但卡复杂度保证的写法。
细节和我犯过的错误
这是个定长的序列，所以我们每次重构的时候可以选择使用构建二叉搜索树的方法线性构建，否者会被卡常。
每次更改节点信息时都要进行复制，
pushdown,merge,split函数和修改操作里都要复制。注意
pushdown和clone的前后顺序。有时候我们并不需要将原节点进行下传标记以免建出无用节点增大常数。注意传参时用的是哪个节点的参数。我曾在
split操作中下传原节点的儿子，实际上是复制后的节点的儿子。FHQ 在新建节点后的
rand值占空间，我们用一段话在merge的时候现场随机，即：rd(0,(e[a].siz+e[b].siz)-1)<e[a].siz可以省下一点空间。
复制和交换的时候记住，给出的区间端点位置可不保证升序的。
重构之后再清空节点数，因为在遍历搜索树的时候会
pushdown而新加节点。
代码
这里的代码是加强版的代码。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<chrono>
#include<random>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
char buf[1 << 21], a[20]; int p, p2 = -1;
inline void flush() {
fwrite(buf, 1, p2 + 1, stdout);
p2 = -1;
}
inline void print(int x) {
if (p2 > 1 << 20) flush();
if (x < 0) buf[++p2] = 45, x = -x;
do a[++p] = x % 10 + 48;while (x /= 10);
do buf[++p2] = a[p];while (--p);
}
namespace star
{
const int maxn=3e5+10,maxm=8e6+10,mod=1e9+7;
mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
int rd(int l,int r){return std::uniform_int_distribution<int>(l,r)(rnd);}
int n,m,a[maxn];
int lastans;
struct FHQ{
#define ls e[ro].son[0]
#define rs e[ro].son[1]
struct node{
int son[2],siz,tag,add,val,sum;
bool rev;
}e[maxm];
int tot,rt;
FHQ():e(),tot(0),rt(0){}
inline void clone(int &x){e[++tot]=e[x],x=tot;}
inline int newnode(const int &a){return e[++tot]=(node){{0,0},1,-1,0,a,a,false},tot;}
inline void pushup(const int &ro){e[ro].siz=e[ls].siz+e[rs].siz+1,e[ro].sum=(1ll*e[ls].sum+e[rs].sum+e[ro].val)%mod;}
void rev(const int &ro){if(ro)e[ro].rev^=1,swap(ls,rs);}
void add(const int &ro,const int &v){if(ro)e[ro].val=(e[ro].val+v)%mod,e[ro].sum=(e[ro].sum+1ll*e[ro].siz*v)%mod,e[ro].add=(e[ro].add+v)%mod;}
void assign(const int &ro,const int &v){if(ro)e[ro].val=v,e[ro].sum=1ll*e[ro].siz*v%mod,e[ro].add=0,e[ro].tag=v;}
inline void pushdown(const int &ro){
if(!e[ro].rev and e[ro].tag==-1 and !e[ro].add) return;
if(ls) clone(ls);if(rs) clone(rs);
if(e[ro].rev) rev(ls),rev(rs),e[ro].rev=false;
if(e[ro].tag!=-1) assign(ls,e[ro].tag),assign(rs,e[ro].tag),e[ro].tag=-1;
if(e[ro].add) add(ls,e[ro].add),add(rs,e[ro].add),e[ro].add=0;
}
int build(const int &l=1,const int &r=n){
if(l>r)return 0;
int mid=(l+r)>>1;
int ro=newnode(a[mid]);
ls=build(l,mid-1),rs=build(mid+1,r);
pushup(ro);
return ro;
}
int merge(int a,int b){
if(!a or !b)return a|b;
if(rd(0,(e[a].siz+e[b].siz)-1)<e[a].siz){
clone(a),pushdown(a);
e[a].son[1]=merge(e[a].son[1],b);
pushup(a);return a;
}else{
clone(b),pushdown(b);
e[b].son[0]=merge(a,e[b].son[0]);
pushup(b);return b;
}
}
void split(int ro,int k,int &a,int &b){
if(!ro) return a=b=0,void();
if(e[ls].siz<k) a=ro,clone(a),pushdown(a),split(e[a].son[1],k-e[e[a].son[0]].siz-1,e[a].son[1],b),pushup(a);
else b=ro,clone(b),pushdown(b),split(e[b].son[0],k,a,e[b].son[0]),pushup(b);
}
inline void copy(){
int l1=read()^lastans,r1=read()^lastans,l2=read()^lastans,r2=read()^lastans,a,b,c,d,e;int bk=1;
if(r1>r2)swap(l1,l2),swap(r1,r2),bk=0;
split(rt,r2,d,e);split(d,l2-1,c,d);split(c,r1,b,c);split(b,l1-1,a,b);
if(bk) rt=merge(a,merge(b,merge(c,merge(b,e))));
else rt=merge(a,merge(d,merge(c,merge(d,e))));
}
inline void Swap(){
int l1=read()^lastans,r1=read()^lastans,l2=read()^lastans,r2=read()^lastans,a,b,c,d,e;
if(r1>r2)swap(l1,l2),swap(r1,r2);
split(rt,r2,d,e);split(d,l2-1,c,d);split(c,r1,b,c);split(b,l1-1,a,b);
rt=merge(a,merge(d,merge(c,merge(b,e))));
}
inline void push(int ro){
if(!ro)return;
pushdown(ro);
push(ls),a[++n]=e[ro].val,push(rs);
}
#undef ls
#undef rs
}S;
inline void work(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
S.rt=S.build();
while(m--){
switch(read()){
case 1:{
int l=read()^lastans,r=read()^lastans,a,b,c;
S.split(S.rt,r,b,c);S.split(b,l-1,a,b);
printf("%d\n",lastans=S.e[b].sum);
S.rt=S.merge(a,S.merge(b,c));
break;
}
case 2:{
int l=read()^lastans,r=read()^lastans,a,b,c;
S.split(S.rt,r,b,c);S.split(b,l-1,a,b);
S.clone(b);
S.assign(b,read()^lastans);
S.rt=S.merge(a,S.merge(b,c));
break;
}
case 3:{
int l=read()^lastans,r=read()^lastans,a,b,c;
S.split(S.rt,r,b,c);S.split(b,l-1,a,b);
S.clone(b);
S.add(b,read()^lastans);
S.rt=S.merge(a,S.merge(b,c));
break;
}
case 4:S.copy();break;
case 5:S.Swap();break;
case 6:{
int l=read()^lastans,r=read()^lastans,a,b,c;
S.split(S.rt,r,b,c);S.split(b,l-1,a,b);
S.clone(b);
S.rev(b);
S.rt=S.merge(a,S.merge(b,c));
break;
}
}
if(S.tot>6500000) n=0,S.push(S.rt),S.rt=S.tot=0,S.rt=S.build();
}
n=0,S.push(S.rt);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
}
signed main(){
star::work();
flush();
return 0;
}
最新文章
- 《C与指针》第十一章练习
- margin:0 auto 与 text-align:center 的区别
- CSS魔法堂：不得不说的Containing Block
- 《Thinking in Java》十七章_容器深入研究_练习13(Page484)
- Asp.net Page指令
- 20145227 《Java程序设计》第5周学习总结
- csdn 刷分小工具(刷了1000多被封了,慎用)
- i2c sub system __i2c_board_list/klist_devices/klist_drivers
- poj 2126 Factoring a Polynomial 数学多项式分解
- c++课程设计之通讯录电话簿管理设计
- asp.net-mvc验证码 asp.net-mvc c#验证码
- 搭建自己的CA服务 - OpenSSL CA 实战
- jQuery UI Autocomplete Combobox 配 ASP.NET DropDownList
- 初识Vulkan
- Oracle表导入Mysql方法
- 11. cookie_session_原生ajax_readyState的值_同源策略_跨域_jsonp的使用
- MHA（下）
- mac上安装虚拟机
- Spring 核心API
- es-05-获取 resthighlevelclient及api