PTA L3 - 区区区间3 (30 分)
题意
输入样例
5 2 3
1 5 3 2 4
2 1 5
1 1 4
输出样例
11
样例解释
进行操作2 1 5后，序列变为1 3 2 5 4
所以操作1 1 4的答案为1+3+2+5=11
附加输入
7 16 4
1 5 3 2 4 6 7
2 2 6
1 1 1 1 2 2 1 3 3 1 4 4 1 5 5 1 6 6 1 7 7
3 3 5
1 1 1 1 2 2 1 3 3 1 4 4 1 5 5 1 6 6 1 7 7
附加输出
1 3 2 4 5 6 7
1 3 5 2 4 6 7
思路
①
首先能够注意到，整组数据中的\(x\)值是定的，所以可以根据序列中每个数与\(x\)之间的大小关系先分成两组
※以附加样例为例，初始数列为\(\{1,5,3,2,4,6,7\}\)，\(x=4\)，分组后得到
\(a[i]\le x\)：\(\{ar\}=\{1,3,2,4\}\)
\(a[i]\gt x\)：\(\{br\}=\{5,6,7\}\)
②
又注意到，不论是操作\(2\)还是操作\(3\)，都没有打乱上述分组的元素之间的顺序
所以不论怎么操作，每组中的数字在原序列中的下标一定是个递增序列
※以附加样例为例，初始时两组数字的下标序列为（按顺序对应数字）
\(a[i]\le x\)：\(\{ar_{pos}\}=\{1,3,4,5\}\)
\(a[i]\gt x\)：\(\{br_{pos}\}=\{2,6,7\}\)
在进行了操作2 2 6后，下标序列变成
\(a[i]\le x\)：\(\{ar_{pos}\}=\{1,2,3,4\}\)
\(a[i]\gt x\)：\(\{br_{pos}\}=\{5,6,7\}\)
再进行操作3 3 5后，下标序列变成
\(a[i]\le x\)：\(\{ar_{pos}\}=\{1,2,4,5\}\)
\(a[i]\gt x\)：\(\{br_{pos}\}=\{3,6,7\}\)
③
于是可以发现，操作\(2\)在下标序列中的修改可以理解成以下几步操作：
1、选出\(\{ar_{pos}\}\)中范围在\([l,r]\)间数字的区间\([r1l,r1r]\)
2、选出\(\{br_{pos}\}\)中范围在\([l,r]\)间数字的区间\([r2l,r2r]\)
3、从\(l\)开始，按顺序先给从\(\{ar_{pos}\}\)中选出的区间重新递增编号
4、（从\(l+r1r-r1l+1\)）开始再按顺序给从\(\{br_{pos}\}\)中选出的区间继续递增编号
操作\(3\)的实质其实就是上面\(3,4\)两步顺序反一下，先给\(\{br_{pos}\}\)编号再给\(\{ar_{pos}\}\)编号
※以附加样例为例，初始时
\(\{ar_{pos}\}=\{1,3,4,5\}\)
\(\{br_{pos}\}=\{2,6,7\}\)
操作2 2 6需要将两序列的值在\([2,6]\)间的区间选出
即选出了\(\{1,\)\(3,4,5\)\(\}\)与\(\{\)\(2,6\)\(,7\}\)
然后先对\(\{ar_{pos}\}\)选出的区间从\(l=2\)开始递增编号，得到\(\{1,2,3,4\}\)
再对\(\{br_{pos}\}\)选出的区间接着编号，得到\(\{5,6,7\}\)
④
再考虑操作\(1\)所要求的输出区间\([l,r]\)之和
根据下标序列的性质，这里的步骤跟③中的步骤差不多
1、选出\(\{ar_{pos}\}\)中范围在\([l,r]\)间数字的区间\([r1l,r1r]\)
2、选出\(\{br_{pos}\}\)中范围在\([l,r]\)间数字的区间\([r2l,r2r]\)
3、输出\(\{ar\}\)的\([r1l,r1r]\)区间和以及\(\{br\}\)的\([r2l,r2r]\)区间和之和作为答案即可
由于②中提及下标序列一定是个递增序列，且没有操作会打乱上述分组的元素之间的顺序
所以\(\{ar\}\)与\(\{br\}\)两数组从头到尾都不会发生改变，可以直接静态求出区间和
（区间和借助前缀和数组\(O(1)\)或者直接放线段树上query \(O(\log n)\)均可）
⑤
对于两种修改操作的下标维护，这里借助两颗线段树对每组下标序列进行
线段树每个节点记录\(l,r,idl,idr,lazy\)，分别为线段左端点，线段右端点，线段中下标最小值，线段中下标最大值，以及懒惰标记
push down (lazy)
由于每次操作都是连续编号的，所以操作后线段长度与下标最值之差是相等的（\(r-l=idr-idl\)）
所以懒惰标记可以以\(0,1\)两种状态来表示子树是否已经更新
如果子树未更新，令\(m=\frac {l+r} 2\)
左子树维护的线段区间是\([l,m]\)，那么其下标最小值与父节点相同，为\(idl\)；下标最大值应为\(idl+(m-l)\)
右子树维护的线段区间是\([m+1,r]\)，那么其下标最大值与父节点相同，为\(idr\)；下标最小值应为\(idr-(r-(m+1))\)，也等于\(idl+(m-l)+1\)
push up
由于下标序列有序，故父节点的\(idl\)等于左子树的\(idl\)，\(idr\)等于右子树的\(idr\)
⑥
由于所有题目中的操作给定的是下标区间\([l,r]\)，而线段树维护的是下标
所以我们应当先将线段树中值在\([l,r]\)间的区间给求出
由于下标有序，所以可以考虑在线段树上二分查找\(l\)与\(r\)两个值
写一个lowerbound函数来求出第一个大于等于\(pos\)的线段树中位置即可
总时间复杂度\(O(n\log n\log n)\)
代码一（前缀和数组求区间和）
#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
typedef long long ll;
const int maxn=200050;
int a[maxn];
int ar[maxn],arpos[maxn],cnta=0;
int br[maxn],brpos[maxn],cntb=0;
ll suma[maxn],sumb[maxn];
struct node
{
int l,r,idl,idr,lazy;
}tra[maxn<<2],trb[maxn<<2];
void push_up(node *tr,int p)
{
tr[p].idl=tr[ls(p)].idl;
tr[p].idr=tr[rs(p)].idr;
}
void push_down(node *tr,int p)
{
if(tr[p].l==tr[p].r)
return;
if(tr[p].lazy)
{
tr[ls(p)].idl=tr[p].idl;
tr[ls(p)].idr=tr[p].idl+(tr[ls(p)].r-tr[ls(p)].l);
tr[rs(p)].idl=tr[ls(p)].idr+1;
tr[rs(p)].idr=tr[p].idr;
tr[ls(p)].lazy=tr[rs(p)].lazy=1;
tr[p].lazy=0;
}
}
void buildTree(node *tr,int l,int r,int *ar,int *arpos,int p=1)
{
tr[p].l=l;
tr[p].r=r;
tr[p].idl=arpos[l];
tr[p].idr=arpos[r];
tr[p].lazy=0;
if(l==r) return;
int m=l+r>>1;
buildTree(tr,l,m,ar,arpos,ls(p));
buildTree(tr,m+1,r,ar,arpos,rs(p));
push_up(tr,p);
}
void update(node *tr,int l,int r,int st,int p=1)
{
if(l>r) return;
int L=tr[p].l,R=tr[p].r;
if(L==l&&R==r) //如果当前线段完全为待更新区间
{
tr[p].idl=st; //从st开始连续编号
tr[p].idr=st+(R-L);
tr[p].lazy=1; //打上懒惰标记
return;
}
push_down(tr,p);
int m=L+R>>1;
if(l<=m) update(tr,l,min(r,m),st,ls(p)); //查询与代表区间最好一致方便处理
if(r>m) update(tr,max(l,m+1),r,st+max(m+1-l,0),rs(p));
push_up(tr,p);
}
int lowerbound(node *tr,int pos,int p=1)
{
if(pos<=tr[p].idl) return tr[p].l;
if(pos>tr[p].idr) return tr[p].r+1;
push_down(tr,p);
int l,r;
l=tr[ls(p)].idl,r=tr[ls(p)].idr;
if(pos>=l&&pos<=r) return lowerbound(tr,pos,ls(p));
l=tr[rs(p)].idl,r=tr[rs(p)].idr;
if(pos>=l&&pos<=r) return lowerbound(tr,pos,rs(p));
return tr[ls(p)].r+1;
}
int main()
{
int n,q,x;
scanf("%d%d%d",&n,&q,&x);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<=x)
{
ar[++cnta]=a[i];
suma[cnta]=suma[cnta-1]+a[i];
arpos[cnta]=i;
}
else
{
br[++cntb]=a[i];
sumb[cntb]=sumb[cntb-1]+a[i];
brpos[cntb]=i;
}
}
buildTree(tra,1,cnta,ar,arpos);
buildTree(trb,1,cntb,br,brpos);
while(q--)
{
int p,l,r;
scanf("%d%d%d",&p,&l,&r);
int r1l=lowerbound(tra,l);
int r1r=lowerbound(tra,r+1)-1;
int r2l=lowerbound(trb,l);
int r2r=lowerbound(trb,r+1)-1;
if(p==1)
printf("%lld\n",max(0LL,suma[r1r]-suma[r1l-1])+max(0LL,sumb[r2r]-sumb[r2l-1]));
else
{
if(p==2)
{
update(tra,r1l,r1r,l);
update(trb,r2l,r2r,l+(r1r-r1l+1));
}
else
{
update(trb,r2l,r2r,l);
update(tra,r1l,r1r,l+(r2r-r2l+1));
}
}
}
return 0;
}
代码二（区间和存线段树中）
#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
typedef long long ll;
const int maxn=200050;
int a[maxn];
int ar[maxn],arpos[maxn],cnta=0;
int br[maxn],brpos[maxn],cntb=0;
struct node
{
int l,r;
int idl,idr;
ll sum;
int lazy;
}tra[maxn<<2],trb[maxn<<2];
void push_up_sum(node *tr,int p)
{
tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
}
void push_up_id(node *tr,int p)
{
tr[p].idl=tr[ls(p)].idl;
tr[p].idr=tr[rs(p)].idr;
}
void push_down(node *tr,int p)
{
if(tr[p].lazy)
{
tr[ls(p)].idl=tr[p].idl;
tr[ls(p)].idr=tr[p].idl+(tr[ls(p)].r-tr[ls(p)].l);
tr[rs(p)].idl=tr[ls(p)].idr+1;
tr[rs(p)].idr=tr[p].idr;
tr[ls(p)].lazy=tr[rs(p)].lazy=1;
tr[p].lazy=0;
}
}
void buildTree(node *tr,int l,int r,int *ar,int *arpos,int p=1)
{
tr[p].l=l;
tr[p].r=r;
tr[p].idl=arpos[l];
tr[p].idr=arpos[r];
tr[p].lazy=0;
if(l==r)
{
tr[p].sum=ar[l];
return;
}
int m=l+r>>1;
buildTree(tr,l,m,ar,arpos,ls(p));
buildTree(tr,m+1,r,ar,arpos,rs(p));
push_up_sum(tr,p);
push_up_id(tr,p);
}
void update(node *tr,int l,int r,int st,int p=1)
{
if(l>r) return;
int L=tr[p].l,R=tr[p].r;
if(L==l&&R==r)
{
tr[p].idl=st;
tr[p].idr=st+(R-L);
if(L!=R) tr[p].lazy=1;
return;
}
push_down(tr,p);
int m=L+R>>1;
if(l<=m) update(tr,l,min(r,m),st,ls(p));
if(r>m) update(tr,max(l,m+1),r,st+max(m+1-l,0),rs(p));
push_up_id(tr,p);
}
ll query(node *tr,int l,int r,int p=1)
{
if(l>r) return 0;
int L=tr[p].l,R=tr[p].r;
if(l<=L&&R<=r) return tr[p].sum;
push_down(tr,p);
int m=L+R>>1;
ll sum=0;
if(l<=m) sum+=query(tr,l,r,ls(p));
if(r>m) sum+=query(tr,l,r,rs(p));
return sum;
}
int lowerbound(node *tr,int pos,int p=1)
{
if(pos<=tr[p].idl) return tr[p].l;
if(pos>tr[p].idr) return tr[p].r+1;
push_down(tr,p);
int l,r;
l=tr[ls(p)].idl,r=tr[ls(p)].idr;
if(pos>=l&&pos<=r) return lowerbound(tr,pos,ls(p));
l=tr[rs(p)].idl,r=tr[rs(p)].idr;
if(pos>=l&&pos<=r) return lowerbound(tr,pos,rs(p));
return tr[ls(p)].r+1;
}
int main()
{
int n,q,x;
scanf("%d%d%d",&n,&q,&x);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<=x)
{
ar[++cnta]=a[i];
arpos[cnta]=i;
}
else
{
br[++cntb]=a[i];
brpos[cntb]=i;
}
}
buildTree(tra,1,cnta,ar,arpos);
buildTree(trb,1,cntb,br,brpos);
while(q--)
{
int p,l,r;
scanf("%d%d%d",&p,&l,&r);
int r1l=lowerbound(tra,l);
int r1r=lowerbound(tra,r+1)-1;
int r2l=lowerbound(trb,l);
int r2r=lowerbound(trb,r+1)-1;
if(p==1)
printf("%lld\n",query(tra,r1l,r1r)+query(trb,r2l,r2r));
else
{
if(p==2)
{
update(tra,r1l,r1r,l);
update(trb,r2l,r2r,l+(r1r-r1l+1));
}
else
{
update(trb,r2l,r2r,l);
update(tra,r1l,r1r,l+(r2r-r2l+1));
}
}
}
return 0;
}
https://blog.csdn.net/qq_36394234/article/details/115871524