题目描述
LuoTianyi gives you an array $ a $ of $ n $ integers and the index begins from $ 1 $ .
Define $ g(i,j) $ as follows:
- $ g(i,j) $ is the largest integer $ x $ that satisfies $ {a_p:i\le p\le j}\subseteq{a_q:x\le q\le j} $ while $ i \le j $ ;
- and $ g(i,j)=0 $ while $ i>j $ .
There are $ q $ queries. For each query you are given four integers $ l,r,x,y $ , you need to calculate $ \sum\limits_{i=l}^{r} \sum\limits_{j=x}^{y} g(i,j) $ .
$ 1\le n,q\le 10^6,1\le a_i\le n, 1\le l\le r\le n, 1\le x\le y\le n $
考虑把答案差分后，扫描线，然后用历史版本和维护答案。
我们现在要尝试在线段树中维护出 \(g(i,r)\)，当 \(r->r+1\) 时维护出 \(g\) 的变换，但是这个不好做。
换个方向，从后往前扫，维护 \(g\)，此时将 \(g(l,i)\) 转到 \(g(l-1,i)\) 时，设 \(a_{l-1}\) 下一次出现的地方为 \(j\)，那么 \([l-1,j]\) 这段区间内的 \(g\) 要覆盖成 \(l-1\)。然后用历史版本和维护答案即可。
题目卡常，要将多个 tag 分别加入。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
int n,T,l[N],r[N],x[N],y[N],nx[N],a[N];
LL ans[N];
vector<pair<int,int> >g[N];
inline int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
struct node{
int c,tg;
LL s,hs,htg;
}tr[N<<2];
void merge(int o,int l,int r,node z)
{
int c=tr[o].c+z.c,tg=tr[o].tg;
LL s=tr[o].s,hs=tr[o].hs+z.c*tr[o].s+z.htg*(r-l+1),htg=tr[o].htg+z.htg;
if(z.tg)
{
s=z.tg*(r-l+1LL);
tg=z.tg;
}
if(tr[o].tg)
{
htg+=1LL*z.c*tr[o].tg;
c-=z.c;
}
tr[o]=(node){c,tg,s,hs,htg};
}
void addc(int o,int l,int r,int c)
{
if(tr[o].tg)
tr[o].htg+=1LL*c*tr[o].tg;
else
tr[o].c+=c;
tr[o].hs+=c*tr[o].s;
}
void addtg(int o,int l,int r,int tg)
{
tr[o].s=tg*(r-l+1LL);
tr[o].tg=tg;
}
void pushdown(int o,int l,int r)
{
int md=l+r>>1;
if(tr[o].c)
{
addc(o<<1,l,md,tr[o].c);
addc(o<<1|1,md+1,r,tr[o].c);
tr[o].c=0;
}
if(tr[o].tg)
{
addtg(o<<1,l,md,tr[o].tg);
addtg(o<<1|1,md+1,r,tr[o].tg);
tr[o].tg=0;
}
if(tr[o].htg)
{
tr[o<<1].htg+=tr[o].htg;
tr[o<<1].hs+=(md-l+1LL)*tr[o].htg;
tr[o<<1|1].htg+=tr[o].htg;
tr[o<<1|1].hs+=1LL*(r-md)*tr[o].htg;
tr[o].htg=0;
}
}
void update(int o,int l,int r,int x,int y,int tg)
{
if(x<=l&&r<=y)
{
addtg(o,l,r,tg);
return;
}
pushdown(o,l,r);
int md=l+r>>1;
if(md>=x)
update(o<<1,l,md,x,y,tg);
if(md<y)
update(o<<1|1,md+1,r,x,y,tg);
tr[o].s=tr[o<<1].s+tr[o<<1|1].s;
tr[o].hs=tr[o<<1].hs+tr[o<<1|1].hs;
}
LL query(int o,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return tr[o].hs;
pushdown(o,l,r);
int md=l+r>>1;
LL ret=0;
if(md>=x)
ret+=query(o<<1,l,md,x,y);
if(md<y)
ret+=query(o<<1|1,md+1,r,x,y);
return ret;
}
int main()
{
n=read(),T=read();
for(int i=1;i<=n;i++)
a[i]=read(),nx[i]=n+1;
for(int i=1;i<=T;i++)
{
l[i]=read(),r[i]=read(),x[i]=read(),y[i]=read();
g[l[i]].push_back(make_pair(i,1));
if(r[i]^n)
g[r[i]+1].push_back(make_pair(i,-1));
}
for(int i=n;i>=1;i--)
{
update(1,1,n,i,nx[a[i]]-1,i);
nx[a[i]]=i;
addc(1,1,n,1);
for(int j=0;j<g[i].size();j++)
ans[g[i][j].first]+=g[i][j].second*query(1,1,n,x[g[i][j].first],y[g[i][j].first]);
}
for(int i=1;i<=T;i++)
printf("%lld\n",ans[i]);
}