魔法少女网站

题解

魔鬼卡常题，我卡了一周的常

由于我们查询的是最大值不大于$x$的区间个数，我们可以考虑将原序列转换成$0/1$序列，小于等于$x$的位置为$1$，大于$x$的位置为$0$，那么我们要求的就是全为$1$的区间个数。
但很明显我们不可能得到整个$0/1$序列后再检查一遍求出答案，我们的在过程中记录下全为$1$的区间，更新答案。
如果要记录的话我们需要尽量将$0$变成$1$，我们将$1$变成$0$的部分是只能通过回退来处理的。
每次我们将$0$变为$1$相当于连接两个全$1$的段，一个长度为$x$的段会产生$\frac{x+x^2}{2}$个子区间，那么我们连接两个长度为$x$与$y$的段带来的答案变化有$\frac{(x+y+1)(x+y+2)}{2}-\frac{x(x+1)}{2}-\frac{y(y+1)}{2}$。
而将$1$变成$0$就只能回退到那个操作在将这个操作逆向回来。

于是我们很快就想到了回滚莫队，我们先将所有的询问按时间排序分块，同一块内的询问再按权值排序。
将所有的数都执行了在这个块之前的操作先全部执行了，反正它们不会影响到我们块内的操作。
由于我们的询问的权值是递增的，所以执行操作后的初始权值对应的点在我们的$0/1$序列中只会不断从$0$变成$1$。
但是，有一部分点是有对应操作与它在一个块中，这部分我们是没法提前处理的，我们只能每次将操作对应的点特殊处理一遍，该询问进行完后再将这些操作去掉，这部分是通过回退去掉的。
这样对于每个询问我们都回回退$O\left(S\right)$，而我们总共会对$O\left(\frac{n}{S}\right)$个串进行操作，每个块的我们都需要将$n$个点加进去，就会有个$O\left(n\right)$的复杂度，所以涉及到块的操作我们时间复杂度是$\left(nS+\frac{n^2}{S}\right)$的。

但我们的询问时区间的询问是区间询问，我们不能直接通过全局的记录得出我们区间询问的答案。
但我们可以考虑对其进行序列分块以求出答案。
我们对于只存在一个块内部的连续段单独记录答案，在操作过程中就存下来，而块块间的我们就记录下上次出现的位置，直到它不能继续延续时再加入答案。
这样我们求答案的时间复杂度也是$O\left(n(S+\frac{n}{S})\right)$。

总时间复杂度 $O\left(nS+\frac{n^2}{S}\right)\geqslant $
按理说我们这样的做法就可以轻松过掉了。
但这道题的出题人是$lxl$，所以这道题很卡常。
你需要手写STL，fread，fwrite以及其余各种优化，顺便卡一下块长，就可以轻松过掉了。
不过好像就我卡了4页常，63发提交可不是虚的

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9;
const int inv2=499122177;
const int jzm=2333;
const int lim=300000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-7;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define getchar gc
char obuf[1<<22],*opt=obuf+(1<<22);
void pc(const int&ch){*--opt=ch;}
#define putchar pc
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){putchar('\n');while(x>9){putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
const int N=MAXN;
int n,m,bl[N],br[N],tim,cd;LL ans[N],wk[N],now[N];
int a[N],al[N],ar[N],sta[N],sd[N],stak,p[N],bk[N];
int vis[N],vp[N],totc,totd,head[N],nxt[N];
struct ming{int opt,l,r,ti,val;bool operator < (const ming &rhs)const{return val<rhs.val;}
}d[N],e[N];
inline void insert(const int ai){a[ai]=1;al[ai]=ar[ai]=ai;int l=ai,r=ai;const int ba=bk[ai];if(a[ai-1]&&bk[ai-1]==ba){l=al[ai-1];now[ba]-=wk[ai-l];ar[al[ai-1]]=ar[ai];al[ai]=al[ai-1];al[ar[ai]]=al[ai];}if(a[ai+1]&&bk[ai+1]==ba){r=ar[ai+1];now[ba]-=wk[r-ai];al[ar[ai+1]]=al[ai];ar[ai]=ar[ai+1];ar[al[ai]]=ar[ai];}now[bk[ai]]+=wk[r-l+1];
}
inline void remove(const int ai){reg int l=ai,r=ai;const int ba=bk[ai];if(a[ai+1]&&bk[ai+1]==ba)al[ar[ai]]=ai+1;if(a[ai-1]&&bk[ai-1]==ba)ar[al[ai]]=ai-1;a[ai]=0;
}
inline void sakura(const int i){for(reg int j=1;j<=n;j++)nxt[j]=head[p[j]],head[p[j]]=j;reg int k=1;sort(d+1,d+totd+1);for(reg int j=1;j<=totd;j++){const int dt=d[j].ti,dv=d[j].val,dl=d[j].l,dr=d[j].r;while(k<=dv){for(reg int k1=head[k];k1;k1=nxt[k1])if(vis[k1]!=i)insert(k1);k++;}stak=ans[dt]=0;for(reg int k1=totc;k1>0;k1--){if(vp[e[k1].l]==dt||e[k1].ti>dt)continue;vp[e[k1].l]=dt;if(e[k1].val<=dv)sta[++stak]=e[k1].l,sd[stak]=now[bk[e[k1].l]],insert(e[k1].l);}for(reg int k1=totc;k1>0;k1--){if(vp[e[k1].l]==dt)continue;if(e[k1].ti<dt)break;vp[e[k1].l]=dt;if(p[e[k1].l]<=dv)sta[++stak]=e[k1].l,sd[stak]=now[bk[e[k1].l]],insert(e[k1].l);}if(bk[dl]==bk[dr]){reg int las=0;for(reg int k1=dl;k1<=dr;k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;ans[dt]+=wk[las];}else{reg int las=0;for(reg int k1=dl;k1<=br[bk[dl]];k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;for(reg int k1=bk[dl]+1;k1<bk[dr];k1++){reg int tmpl=a[bl[k1]]?ar[bl[k1]]-bl[k1]+1:0;reg int tmpr=a[br[k1]]?br[k1]-al[br[k1]]+1:0;if(tmpl==br[k1]-bl[k1]+1)las+=tmpl;else ans[dt]+=now[k1]+wk[las+tmpl]-wk[tmpl]-wk[tmpr],las=tmpr;}for(reg int k1=bl[bk[dr]];k1<=dr;k1++)if(a[k1])las++;else ans[dt]+=wk[las],las=0;ans[dt]+=wk[las];}while(stak)now[bk[sta[stak]]]=sd[stak],remove(sta[stak--]);}for(reg int j=1;j<=totc;j++)p[e[j].l]=e[j].val;totc=totd=0;for(reg int j=1;j<=n;j++)a[j]=head[j]=0;for(reg int j=1;j<=bk[n];j++)now[j]=0;
}
signed main(){read(n);read(m);tim=1;const int n1=sqrt(n);for(reg int i=1;i<=n;i++)read(p[i]);for(reg int i=1;i<=n;i++)wk[i]=1ll*i*(i+1)/2LL;for(reg int i=1;i<=n;i++){bk[i]=(i+n1-1)/n1;if(!bl[bk[i]])bl[bk[i]]=i;br[bk[i]]=i;}for(reg int i=1;i<=m;i++){reg int opt;read(opt);ans[i]=-1;ming s;if(opt==1){reg int x,y;read(x);read(y);e[++totc]=(ming){1,x,0,i,y};vis[x]=tim;}else{reg int l,r,x;read(l);read(r);read(x);d[++totd]=(ming){2,l,r,i,x};}if(totc+totd==2000||i==m)sakura(tim),tim++;}for(int i=m;i>0;i--)if(ans[i]>=0)print(ans[i]);fwrite(opt,1,obuf+(1<<22)-opt,stdout);return 0;
}

谢谢！！！！