CF1824D LuoTianyi and the Function 推标记 区间历史版本和
Linnyx
·
·
题解
考虑去拆 \displaystyle \sum_{i=l}^{r}\sum_{j=x}^{y}g(i,j) 的贡献：
\displaystyle \sum_{i=l}^{r}\sum_{j=x}^{y}g(i,j)=\sum_{i=l}^{r}\sum_{j=1}^{y}g(i,j)-\sum_{i=l}^{r}\sum_{j=1}^{x-1}g(i,j)
题目告诉我们当 i>j 时 g(i,j) 的贡献为 0，所以我们可以进一步把式子写成：
\sum_{i=l}^{min(r,y)}\sum_{j=1}^{y}g(i,j)-\sum_{i=l}^{min(r,x-1)}\;\sum_{j=1}^{x-1}g(i,j)
这是一个历史版本和问题，多组询问离线用扫描线维护。
设 F_i 为在 i 位置（包括 i 位置）之后 a_{i} 出现的次数。
假设我们现在处理到 j，g(i,j) 的值为 i 之后第一个出现 F_x=1 的位置。
它影响的区间是从 x 的位置之前再一个 F_y=1 的位置的后一个位置到 x
（区间）即 y+1\sim x
我们从左向右依次加入 a_{i}，每次加入看作一个新的版本。
如果 a_{i} 在之前出现过，我们考虑对其影响：
此时局面
加入 a_{i} 后，F_{pre_{a_{i}}} 就不是 1 了。
我们修改贡献，得：
发现这是一个区间覆盖。
加入其贡献后，再使线段树上 1\sim i 区间维护的当前版本加入历史版本和。
这是一个区间加。
所以我们需要一颗区间覆盖区间加线段树。
考虑推标记（懒可以直接矩阵，就是可能要卡常或者拆，我太菜了不会）
大佬 Ckain 的矩阵版：blog
一共维护 3 个标记：
因为 $tga$ 是依赖于当前版本，所以它的优先级应该高于 $tgcv$。
将每个节点的标记看作一个队列，同种可合并，但是相隔 $tgcv$ 的两个 $tga$ 并不可以合并，原因就是刚刚说的，$tga$ 是依赖于当前版本，$tgcv$ 更改了当前版本，两个 $tga$ 依赖的不是同一个版本，但是在 $tgcv$ 后的 $tga$ 会退化成 $tgc$（可直接算出，直接变成常数。
可以结合以下代码理解：
```cpp
void addx(int p,int x){//加法标记
t[p].hd+=x*t[p].d;
if(t[p].tg.cx)t[p].tg.c1+=x*t[p].tg.cx;
else t[p].tg.addx+=x;
}
void addc(int p,int x){//常数标记
t[p].hd+=x*t[p].len;
t[p].tg.c1+=x;
}
void cx(int p,int x){//覆盖标记
t[p].d=x*t[p].len;
t[p].tg.cx=x;
}
void pd(int p){
if(t[p].tg.addx)addx(ls,t[p].tg.addx),addx(rs,t[p].tg.addx);
if(t[p].tg.c1)addc(ls,t[p].tg.c1),addc(rs,t[p].tg.c1);
if(t[p].tg.cx)cx(ls,t[p].tg.cx),cx(rs,t[p].tg.cx);
t[p].tg={0,0,0};
}
```
还有细节问题可参考代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd(void){
int s=0, f=1; char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=0; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-'0'; c=getchar();}
return f? s:-s;
}
const int N=1e6+10;
int n,m;
int a[N];
struct tag{
int addx,cx,c1;
};
struct node{
tag tg;
int hd,d,len,l,r;
}t[N<<2];
#define ls p*2
#define rs p*2+1
#define mid (t[p].l+t[p].r)/2
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;t[p].len=(r-l+1);
if(l==r)return ;
build(ls,l,mid);
build(rs,mid+1,r);
}
void addx(int p,int x){//加法标记
t[p].hd+=x*t[p].d;
if(t[p].tg.cx)t[p].tg.c1+=x*t[p].tg.cx;
else t[p].tg.addx+=x;
}
void addc(int p,int x){//常数标记
t[p].hd+=x*t[p].len;
t[p].tg.c1+=x;
}
void cx(int p,int x){//覆盖标记
t[p].d=x*t[p].len;
t[p].tg.cx=x;
}
void pd(int p){
if(t[p].tg.addx)addx(ls,t[p].tg.addx),addx(rs,t[p].tg.addx);
if(t[p].tg.c1)addc(ls,t[p].tg.c1),addc(rs,t[p].tg.c1);
if(t[p].tg.cx)cx(ls,t[p].tg.cx),cx(rs,t[p].tg.cx);
t[p].tg={0,0,0};
}
void pu(int p){
t[p].hd=t[ls].hd+t[rs].hd;
t[p].d=t[ls].d+t[rs].d;
}
void upd(int p,int l,int r,int v,int f){
//if(l>r)return ;
if(t[p].l==l&&t[p].r==r){
if(f)addx(p,v);
else cx(p,v);
return ;
}
pd(p);
if(r<=mid)upd(ls,l,r,v,f);
else if(l>mid)upd(rs,l,r,v,f);
else{
upd(ls,l,mid,v,f);upd(rs,mid+1,r,v,f);
}
pu(p);
}
int query(int p,int l,int r){
//if(l>r)return 0;
if(t[p].l==l&&t[p].r==r){
return t[p].hd;
}
pd(p);
if(r<=mid)return query(ls,l,r);
else if(l>mid)return query(rs,l,r);
else{
return query(ls,l,mid)+query(rs,mid+1,r);
}
}
#undef ls
#undef rs
#undef mid
struct Que{
int l,r,f,id;
};
vector<Que> que[N];
set<int> st;
int pre[N],ans[N],pos[N];
signed main(){
n=rd();m=rd();
for(int i=1;i<=n;i++)a[i]=rd();
for(int i=1;i<=m;i++){
int l=rd(),r=rd(),x=rd(),y=rd();
que[y].push_back({l,min(y,r),1,i});
que[x-1].push_back({l,min(x-1,r),-1,i});
}
build(1,1,n);
st.insert(0);
for(int i=1;i<=n;i++){
if(pre[a[i]]){
auto it=st.lower_bound(pre[a[i]]);
int l=*(--it);++it;
int v=((++it)==st.end())?i:*it;--it;
upd(1,l+1,pre[a[i]],v,0);
st.erase(it);
}
pre[a[i]]=i;
st.insert(i);
upd(1,i,i,i,0);
upd(1,1,i,1,1);
for(Que k:que[i]){
if(k.l<=k.r)ans[k.id]+=k.f*query(1,k.l,k.r);
}
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans[i]);
}
return 0;
}
```