题解：P7983 [JRKSJ R3] practiceZ
总算卡过了。具体就是块长开大，换 C++98。
可爱的分块题。
考虑对序列
先不考虑
每次我们对
对于前缀和，区间加转化为两次等差数列加即可，一次等差数列加的贡献记为：
考虑整块贡献，每次直接取所有
加入对于序列
考虑一个不好的事情：
分块后被散块修改的区间都需要重置，要求重置做到
首先考虑需要什么样的数据结构可以维护：
对于线性次修改，我们只需要维护一个
问题在于散块的修改是
考虑如何不全部重构？即想让修改次数转化为线性。
有以下的结论：
序列分块下，在所有块内部维护珂朵莉树，总复杂度为
则我们先对序列分块，一次推平操作，整块打标记（注意这里不能直接打，如果之前有散区间需要先清空，有标记的区间直接通过标记加贡献），散块对珂朵莉树修改，改贡献。
则我们需要统计的信息有：
没了，总共需要写三个分块，两棵珂朵莉树，注意以下离线操作和升天的常数。
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void in(T &n){
n=0;char c=getchar();bool flag=0;
for(;c<'0'||c>'9';c=getchar()) if (c=='-') flag=1;
for(;c>='0'&&c<='9';c=getchar()) (n*=10)+=(c^48);
if (flag) n=-n;
}
int wlsk[45];int wltp;
template<typename T>
void out(T n,char c=0){
if (n==0){putchar('0');if (c)putchar(c);return ;}
if (n<0) putchar('-'),n=-n;
while(n) wlsk[++wltp]=(n%10),n/=10;
while(wltp) putchar(wlsk[wltp--]^48);
if (c) putchar(c);
}
typedef unsigned int ll1;
#define int ll1
const int N=5e5+5;
const int MaxB=1005;
struct Node{
int l,r;
ll1 dt;
bool operator <(const Node&o)const{return l<o.l;}
};
int n,q;
int a[N],b[N];
ll1 sb[N];
vector<pair<int,int> >opers[N];//区间加:大于 x 的元素+y(pos-x)
#define mkp make_pair
namespace Chtholly{
set<Node>s;
void build(){
for(int r=1;r<=n;r++){
int l=r;
while(a[r+1]==a[r]&&r<n)++r;
s.insert((Node){l,r,(ll1)a[l]});
}
}
set<Node>::iterator iter,iter1,iter2;
void split(int dv){//划分为 dv-1,dv
iter=--(s.upper_bound((Node{dv,0,0})));
if(iter->l>=dv)return;
Node tmp=*iter;s.erase(iter);
s.insert((Node){tmp.l,dv-1,tmp.dt});
s.insert((Node){ dv ,tmp.r,tmp.dt});
}
void mer(set<Node>::iterator iter){
if(iter==s.end()||iter==s.begin())return;
iter1=iter--;
if(iter1->dt!=iter->dt)return;
Node tmp=(Node){iter->l,iter1->r,iter->dt};
s.erase(iter,++iter1);
s.insert(tmp);
}
void push_off(int l,int r,int x,int t){
split(l),split(r+1);
iter1=s.lower_bound((Node){l,0,0});
iter2=s.upper_bound((Node){r,0,0});
for(iter=iter1;iter!=iter2;++iter){
opers[t].push_back(mkp((iter->l)-1,x-(iter->dt)));
opers[t].push_back(mkp((iter->r),(iter->dt)-x));
}
s.erase(iter1,iter2);
s.insert((Node){l,r,(ll1)x});
mer(s.upper_bound((Node){r,0,0}));
mer(s.lower_bound((Node){l,0,0}));
}
}
namespace block_A{//后缀加，单点查前缀和
int B,tb=0;
int L[N],R[N],bel[N];
ll1 K[N],adtg[N];
ll1 sum[N];
void build(){
B=sqrt(n);
L[tb=0]=-B;
for(int i=1;i<=n;i++){
if(L[tb]+B<=i)L[++tb]=i;
R[tb]=i,bel[i]=tb;
}
ll1 sm=0;
for(int o=1;o<=tb;o++){
int l=L[o],r=R[o];
adtg[o]=K[o]=0;
for(int i=l;i<=r;i++){
sm+=a[i];
sum[i]=sm;
}
}
}
void add(int st,ll1 k){
for(int o=bel[st+1];o<=tb;o++){
int l=L[o],r=R[o];
if(l>=st){
K[o]+=k,adtg[o]+=ll1(l-st)*k;
}else for(int i=max(l,st);i<=r;i++)sum[i]+=(i-st)*k;
}
}
ll1 query(int x){
return adtg[bel[x]]+sum[x]+K[bel[x]]*(x-L[bel[x]]);
}
}
namespace block_V{//单点加，区间查后缀和
int B,tb=0;
int L[N],R[N],bel[N];
ll1 sumb[N],cntb[N],sum[N],cnt[N];
void build(){//这个是主要的花销
B=sqrt(n);
L[tb=0]=-B;
for(int i=1;i<=n;i++){
if(L[tb]+B<=i)L[++tb]=i;
R[tb]=i,bel[i]=tb;
}
}
void clear(){
for(int i=1;i<=n;i++)sum[i]=cnt[i]=0;
for(int o=1;o<=tb;o++)cntb[o]=sumb[o]=0;
}
void add(int x,ll1 c){
for(int o=bel[x];o;o--){
int l=L[o],r=R[o];
if(r<=x)sumb[o]+=c*x,cntb[o]+=c;
else for(int i=x;i>=l;i--)cnt[i]+=c,sum[i]+=c*x;
}
}
ll1 querysm(int x){
if(!x)x=1;
return sumb[bel[x]]+sum[x];
}
ll1 querycnt(int x){
if(!x)x=1;
return cntb[bel[x]]+cnt[x];
}
}
namespace block{
int B,tb=0;
int L[N],R[N],bel[N];
ll1 sm[N];//总和
int tagc[N];
int b1[N];
void build(){
B=sqrt(n*14);
L[tb=0]=-B;
for(int i=1;i<=n;i++){
if(L[tb]+B<=i)L[++tb]=i;
R[tb]=i,bel[i]=tb;
b1[i]=b[i];
}
for(int o=1;o<=tb;o++){
sm[o]=0;tagc[o]=0;
for(int i=L[o];i<=R[o];i++)
sm[o]+=sb[i];
}
}
}
struct OPER{int c;int dt;ll1 w;int t;};vector<OPER>rplc[N];
//每个时间的替换方案：从给块 A 增加/减去了 c 个 dt，
//此时在 A 中权值为 w。
struct ODT{
set<Node>s;
void build(int L,int R){
for(int r=L;r<=R;r++){
int l=r;
while(b[r+1]==b[r]&&r<R)++r;
s.insert((Node){l,r,(ll1)b[l]});
}
}
set<Node>::iterator iter,iter1,iter2;
void split(int dv){//划分为 dv-1,dv
iter=s.upper_bound((Node{dv,0,0}));
if(iter==s.begin())return;
--iter;
if(iter->l>=dv)return;
Node tmp=*iter;s.erase(iter);
s.insert((Node){tmp.l,dv-1,tmp.dt});
s.insert((Node){ dv ,tmp.r,tmp.dt});
}
void mer(set<Node>::iterator iter){
if(iter==s.end()||iter==s.begin())return;
iter1=iter--;
if(iter1->dt!=iter->dt)return;
Node tmp=(Node){iter->l,iter1->r,iter->dt};
s.erase(iter,++iter1),s.insert(tmp);
}
void push_off(int l,int r,int x,int o,int t){
split(l),split(r+1);
iter1=s.lower_bound((Node){l,0,0});
iter2=s.upper_bound((Node){r,0,0});
for(iter=iter1;iter!=iter2;++iter){
rplc[o].push_back((OPER){-((iter->r)-(iter->l)+1),int(iter->dt),block_A::query(iter->dt),t});
}//删除段
s.erase(iter1,iter2);
s.insert((Node){l,r,(ll1)x});
mer(s.upper_bound((Node){r,0,0}));
mer(s.lower_bound((Node){l,0,0}));
}
void push_off1(int l,int r,int x){//不产生贡献
split(l),split(r+1);
iter1=s.lower_bound((Node){l,0,0});
iter2=s.upper_bound((Node){r,0,0});
s.erase(iter1,iter2);
s.insert((Node){l,r,(ll1)x});
mer(s.upper_bound((Node){r,0,0}));
mer(s.lower_bound((Node){l,0,0}));
}
}odts[MaxB];
int OP[N],Lt[N],Rt[N],Dt[N];
ll1 Vals[N],Ans[N];
void init(){
in(n),in(q);
ll1 sma[N];
for(int i=1;i<=n;i++)
in(a[i]),sma[i]=sma[i-1]+a[i];
for(int i=1;i<=n;i++)
in(b[i]),sb[i]=sma[b[i]];
Chtholly::build();//大珂朵莉
for(int t=1;t<=q;t++){
in(OP[t]),in(Lt[t]),in(Rt[t]);
if(OP[t]<3)in(Dt[t]);
if(OP[t]==1)Chtholly::push_off(Lt[t],Rt[t],Dt[t],t);//记录 Chtholly 操作
}
}
void prework(){//第一次离线操作
block_A::build();
block::build();
for(int o=1;o<=block::tb;o++)//小珂朵莉
odts[o].build(block::L[o],block::R[o]);
for(int t=1;t<=q;t++){
int lt=Lt[t],rt=Rt[t];
if(OP[t]==1){
for(ll1 xx=0;xx<opers[t].size();xx++){
pair<int,int> df=opers[t][xx];
block_A::add(df.first,df.second);//修改
}
continue;
}
if(OP[t]==2){//修改 B 序列
using namespace block;
Vals[t]=block_A::query(Dt[t]);
for(int o=bel[lt];o<=bel[rt];o++){//对每个块内的 ODT 操作
int l=L[o],r=R[o];//珂朵莉修改
if(l>=lt&&r<=rt){
if(!tagc[o])//清空，放入 tag
odts[o].push_off(l,r,Dt[t],o,t);
tagc[o]=Dt[t];//整块不贡献到 ODT 上
}else{//散块
if(tagc[o]){
for(int i=l;i<=r;i++)b1[i]=tagc[o];
//在值域分块上打上整块
rplc[o].push_back((OPER){r-l+1,tagc[o],block_A::query(tagc[o]),t});
odts[o].push_off1(l,r,tagc[o]);//在珂朵莉树上打标记，不用删除旧贡献（因为没有加上）
tagc[o]=0;
}
odts[o].push_off(max(l,lt),min(r,rt),Dt[t],o,t);
rplc[o].push_back((OPER){min(r,rt)-max(l,lt)+1,Dt[t],block_A::query(Dt[t]),t});
for(int i=max(l,lt);i<=min(r,rt);i++)b1[i]=Dt[t];
//这样就处理了所有的整块 sum 变化量
}
}
continue;
}
if(OP[t]==3){
using namespace block;
for(int o=bel[lt];o<=bel[rt];o++){
if(L[o]>=lt&&R[o]<=rt)continue;
for(int i=max(L[o],lt);i<=min(R[o],rt);i++)
Ans[t]+=block_A::query(tagc[o]?tagc[o]:b1[i]);
}
}
}
}
vector<OPER>opint[N];
void solve(int o){
block_V::clear();
int l=block::L[o],r=block::R[o],len=r-l+1;
for(int i=l;i<=r;i++)
block_V::add(b[i],1);
int nwtg=0;//当前的整块标记
ll1 sm=block::sm[o];//初始的和
for(int t=1;t<=q;t++)opint[t].clear();
for(int xx=0;xx<rplc[o].size();xx++){
OPER cq=rplc[o][xx];
opint[cq.t].push_back(cq);
}
for(int t=1;t<=q;t++){
int lt=Lt[t],rt=Rt[t];
if(OP[t]==1){//对于值域做修改
for(int xx=0;xx<opers[t].size();xx++){
pair<int,int> cq=opers[t][xx];
if(nwtg){
if(nwtg>=cq.first)
sm+=len*(nwtg-cq.first)*cq.second;
}else sm+=(-(block_V::querycnt(cq.first)*cq.first)+block_V::querysm(cq.first))*cq.second;
}
}
if(OP[t]==2){//修改 B 序列，分 tag 和非 tag 处理
for(int xx=0;xx<opint[t].size();xx++){//修改值域分块
OPER cq=opint[t][xx];
block_V::add(cq.dt,cq.c);
}
if(l>=lt&&r<=rt){//整块，打 tag
nwtg=Dt[t];
sm=len*Vals[t];//直接覆盖，更新 sm
}else if(!(r<lt||l>rt)){
if(nwtg){
nwtg=0;//破坏整块，不仅重置分块还要重置 sm
sm=0;
}
for(int xx=0;xx<opint[t].size();xx++){
OPER cq=opint[t][xx];
sm+=cq.w*cq.c;
}
}
}
if(OP[t]==3&&l>=lt&&r<=rt)
Ans[t]+=sm;
}
}
void work(){
block_V::build();
block::build();
for(int o=1;o<=block::tb;o++)solve(o);
for(int t=1;t<=q;t++){
if(OP[t]<3)continue;
out(Ans[t],'\n');
}
}
signed main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
init();
prework();
work();
return 0;
}
/*
考虑我们块内维护有关 B_i 的值域分块
则我们需要推平某种元素的时候：（散块）
直接对它做修改。
否则我们推平这个东西，之后打整块标记（整块不满足总修改线性）
*/