当前位置：首页 > news >正文

一些 DS 题目

news 2025/8/17 12:27:10

1.nfls #1194 3的倍数区间

题意

给定一个长度为的数组,有次修改，每次把数组中某个元素改成其他的数或者询问一个区间中有多少个子区间满足和为 $3$ 的倍数。

$n,m≤3×105n,m\le 3\times 10^5$ 。

思路

和为倍数的，得先想到把余数分类开来，反正这里余数只有 $0, 1, 2$ 。

注意到题目问的是子区间的个数。联想到维护最大子段和的思路：在线段树上维护区间的和、前缀和、后缀和、子段和答案。

于是同样考虑，维护区间 $mod3\bmod 3$ 的和 $s u m$ 、前后缀余 $0, 1, 2$ 的桶 l[],r[]，以及区间答案 $an s$ ，容易用两个桶维护 $an s$ ，将余数和为 $0$ 的合并，考虑合并函数：

node add(const node a,const node b)
{node ret;ret.sum=(a.sum+b.sum)%3;ret.ans=a.ans+b.ans+a.r[0]*b.l[0]+a.r[1]*b.l[2]+a.r[2]*b.l[1];//乘法原理计算方案数for(int i=0;i<3;i++){ret.l[i]+=a.l[i];ret.l[(i+a.sum)%3]+=b.l[i];//囊括一整段ls查看触及到rs的l端 ret.r[i]+=b.r[i];ret.r[(i+b.sum)%3]+=a.r[i];}	return ret;
}

对于单点修改直接对四者初始化，照线段树常例 pushup 和 query。平日里求和的 query 是可以直接相加，但是这里使用 add 函数，不能用一个全空的结构体变量参与运算，因此要把合并区间答案的给拎出来——对于返回结构体的 query，使用 add 合并区间答案的，都适用以下写法：

node query(ll u,ll l,ll r,ll ql,ll qr)
{if(ql<=l&&r<=qr)return T[u];ll mid=(l+r)>>1;if(qr<=mid)return query(ls,l,mid,ql,qr);if(ql>mid)return query(rs,mid+1,r,ql,qr);return add(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));}

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=3e5+9;
ll n,Q;
ll a[N];
struct SegT
{struct node{ll sum;//模3区间和 ll ans;ll l[3]={0,0,0},r[3]={0,0,0};//前后缀和每个余数的桶 void init(ll k){sum=k%3;ans=(k%3==0);for(int i=0;i<3;i++)l[i]=r[i]=0;l[k%3]=r[k%3]=1;}}T[N<<2];node add(const node a,const node b){node ret;ret.sum=(a.sum+b.sum)%3;ret.ans=a.ans+b.ans+a.r[0]*b.l[0]+a.r[1]*b.l[2]+a.r[2]*b.l[1];for(int i=0;i<3;i++){ret.l[i]+=a.l[i];ret.l[(i+a.sum)%3]+=b.l[i];//囊括一整段ls查看触及到rs的l端 ret.r[i]+=b.r[i];ret.r[(i+b.sum)%3]+=a.r[i];}	return ret;}void pushup(ll u){T[u]=add(T[ls],T[rs]);}void build(ll u,ll l,ll r){if(l==r){T[u].init(a[l]);return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void modify(ll u,ll l,ll r,ll x,ll k){if(l==r){T[u].init(k);return;}ll mid=(l+r)>>1;if(x<=mid)modify(ls,l,mid,x,k);if(x>mid)modify(rs,mid+1,r,x,k);pushup(u);}node query(ll u,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr)return T[u];ll mid=(l+r)>>1;if(qr<=mid)return query(ls,l,mid,ql,qr);if(ql>mid)return query(rs,mid+1,r,ql,qr);return add(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));}
}A;
int main()
{scanf("%lld%lld",&n,&Q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);A.build(1,1,n);while(Q--){ll op,l,r;scanf("%lld%lld%lld",&op,&l,&r);if(op==1)A.modify(1,1,n,l,r);else printf("%lld\n",A.query(1,1,n,l,r).ans);}return 0;
}

2.#5798 维护序列 / 洛谷 P2023 AHOI2009 维护序列

题意

题目传送门，就是区间的加、乘操作，然后查询区间和。

思路

只是在这里贴一个区间加、乘线段树的模板。要记得：

下放 $t a g$ 的时候，要先放乘法再放加法；
初始化乘法 $t a g$ 为 $1$ ，加法 $t a g$ 为 $0$ ；
加法只对加法 $t a g$ 有影响，乘法对 $2$ 个 $t a g$ 都有影响；
反正修改之前都会下放标记，因此先乘后加的顺序符合运算律。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e5+9;
ll n,mod,a[N],q;
struct SegT
{struct node{ll sum;//区间答案 ll tag1,tag2;//加法tag 乘法tag }T[N<<2];void pushup(ll u){T[u].sum=(T[ls].sum+T[rs].sum)%mod;}void modi(ll u,ll l,ll r,ll tg1,ll tg2){T[u].sum=(T[u].sum*tg2%mod+(r-l+1)*tg1%mod)%mod;T[u].tag2=T[u].tag2*tg2%mod;T[u].tag1=(T[u].tag1*tg2%mod+tg1)%mod; }void pushdown(ll u,ll l,ll r){ll mid=(l+r)>>1;modi(ls,l,mid,T[u].tag1,T[u].tag2);modi(rs,mid+1,r,T[u].tag1,T[u].tag2);T[u].tag1=0,T[u].tag2=1;}void build(ll u,ll l,ll r){T[u].tag1=0;T[u].tag2=1;if(l==r){T[u].sum=a[l];return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void add(ll u,ll l,ll r,ll ql,ll qr,ll k){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].sum+=(r-l+1)*k;T[u].tag1+=k;return;}pushdown(u,l,r);ll mid=(l+r)>>1;if(ql<=mid)add(ls,l,mid,ql,qr,k);if(qr>mid)add(rs,mid+1,r,ql,qr,k);pushup(u);}void mul(ll u,ll l,ll r,ll ql,ll qr,ll k){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].sum=T[u].sum*k%mod;T[u].tag1=T[u].tag1*k%mod;T[u].tag2=T[u].tag2*k%mod;return;}pushdown(u,l,r);ll mid=(l+r)>>1;if(ql<=mid)mul(ls,l,mid,ql,qr,k);if(qr>mid)mul(rs,mid+1,r,ql,qr,k);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr)return T[u].sum;pushdown(u,l,r);ll mid=(l+r)>>1,sum=0;if(ql<=mid)sum=(sum+query(ls,l,mid,ql,qr))%mod;if(qr>mid)sum=(sum+query(rs,mid+1,r,ql,qr))%mod;return sum;}
}A;
int main()
{scanf("%lld%lld",&n,&mod);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);A.build(1,1,n);scanf("%lld",&q);while(q--){ll op,l,r,x;scanf("%lld%lld%lld",&op,&l,&r);if(op==1){scanf("%lld",&x);A.mul(1,1,n,l,r,x);}if(op==2){scanf("%lld",&x);A.add(1,1,n,l,r,x);}if(op==3)printf("%lld\n",A.query(1,1,n,l,r));}return 0;
}

洛谷 P1471 方差，拆式子之后，就是运用区间加乘线段树。

3.nfls #3594 打怪升级 / HDU3954 Level Up

题意

在这里插入图片描述

思路

真是把线段树玩出花了，这种题怎么能只放在 E. 的？

考虑维护维护区间经验值最大值 $ma$ ，等级最大值 $l e v e l$ （最大等级打怪，是与经验最大值修改强相关的）。因为涉及区间修改，于是维护击杀怪兽后下放的血量的 $e$ 的 $t a g$ 。

这题其实最头疼的是升级：在打了很多怪之后，每个英雄的等级都不一样，升级所需的经验值也各不相同——看起来就很不可做啊。

zc 说可以考虑，对于每个英雄可以升到下一级的所需经验值的最小值，但是对于每个英雄的经验增长量都不同：因此直接维护区间内英雄距离下一次升级需要的经验值和等级之比的最小值 $N e d$ 。这样子，每次就是和怪兽的血量 $e$ （即 $t a g$ ）直接运算。

当做到一个 $Ned≤0Ned\le 0$ 时，说明该区间存在可以升级的英雄。因此直接暴力下方标记、查找 $Ned≤0Ned\le 0$ 的具体下标，然后暴力修改这个英雄的 $l e v e l$ 和 $N e d$ 。

void modi(ll u,ll l,ll r,ll tg)//maintain
{T[u].Ned-=tg;T[u].tag+=tg;T[u].ma+=T[u].level*tg;if(T[u].Ned<=0){if(l==r){T[u].tag=0;while(T[u].ma>=need[T[u].level+1])T[u].level++;ll dist=need[T[u].level+1]-T[u].ma;T[u].Ned=dist/T[u].level+(dist%T[u].level==0?0:1);}else{ll mid=(l+r)>>1;modi(ls,l,mid,T[u].tag);//向下找具体哪一个可以升级了，顺便把沿路的数据修改了 modi(rs,mid+1,r,T[u].tag);T[u].tag=0;pushup(u);}}
}

（我觉得又难写又难想，放弃挣扎了对着题解打的……）

每次区间修改要修改和查找一遍，然后 pushdown 也要搞一次查找和升级。然后询问过程中也会 pushdown 很多次，因此 $l e v e l$ 、 $N e d$ 、 $ma$ 都可能改变，所以每次后面都要接 pushup 操作。

（只能说我的马蜂还行了，欢迎批评）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e4+9,inf=3e14;
ll T,n,k,Q;
ll need[N];
struct SegT
{struct node{ll ma;//最大经验值 ll tag;//怪物下放了的经验值 ll level,Ned;//区间内某一元素，距离下一次升级需要的最小的经验值和等级之比//消除等级对修改的影响}T[N<<2];void pushup(ll u){T[u].ma=max(T[ls].ma,T[rs].ma);T[u].level=max(T[ls].level,T[rs].level);T[u].Ned=min(T[ls].Ned,T[rs].Ned);}void modi(ll u,ll l,ll r,ll tg){T[u].Ned-=tg;T[u].tag+=tg;T[u].ma+=T[u].level*tg;if(T[u].Ned<=0){if(l==r){T[u].tag=0;while(T[u].ma>=need[T[u].level+1])T[u].level++;ll dist=need[T[u].level+1]-T[u].ma;T[u].Ned=dist/T[u].level+(dist%T[u].level==0?0:1);}else{ll mid=(l+r)>>1;modi(ls,l,mid,T[u].tag);//向下找具体哪一个可以升级了，顺便把沿路的数据修改了 modi(rs,mid+1,r,T[u].tag);T[u].tag=0;pushup(u);}}}void pushdown(ll u,ll l,ll r){ll mid=(l+r)>>1;modi(ls,l,mid,T[u].tag);modi(rs,mid+1,r,T[u].tag);T[u].tag=0;}void build(ll u,ll l,ll r){T[u]={0,0,0,0};if(l==r){T[u].ma=0;T[u].level=1;T[u].Ned=need[2];return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void modify(ll u,ll l,ll r,ll ql,ll qr,ll e){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){modi(u,l,r,e);return;}pushdown(u,l,r);ll mid=(l+r)>>1;if(ql<=mid)modify(ls,l,mid,ql,qr,e);if(qr>mid)modify(rs,mid+1,r,ql,qr,e);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr)return T[u].ma;pushdown(u,l,r);ll mid=(l+r)>>1,ret=-inf;if(ql<=mid)ret=max(ret,query(ls,l,mid,ql,qr));if(qr>mid)ret=max(ret,query(rs,mid+1,r,ql,qr));pushup(u);//pushdown过程中随时会升级，所以要pushup return ret;}
}A;
int main()
{ll tick=0;scanf("%lld",&T);while(T--){tick++;printf("Case %lld:\n",tick);scanf("%lld%lld%lld",&n,&k,&Q);for(int i=2;i<=k;i++)scanf("%lld",&need[i]);need[k+1]=inf;A.build(1,1,n);while(Q--){char op;ll l,r,e;cin>>op;scanf("%lld%lld",&l,&r);if(op=='W'){scanf("%lld",&e);A.modify(1,1,n,l,r,e);}else printf("%lld\n",A.query(1,1,n,l,r));}} return 0;
}

4.nfls #21689 化学实验 / CF431E Chemistry Experiment

题意

有 $n$ 支试管，每支试管装有 $himlh_i\ \mathrm{ml}$ 的水银。 $q$ 次操作，有两种操作：

1 p v：将试管 $p$ 的水银修改为 $vmlv\ \mathrm{ml}$ ；
2 v：将 $vmlv\ \mathrm{ml}$ 水任意分配到 $n$ 支试管内，最小化有水的试管中的最大体积，输出这个最小值（误差不超过 $10^{-4}$ 算正确）
注意，倒水操作并不会影响后面的询问，即倒水只是假想操作，并不会真正倒水。

$n,q≤105n,q\le 10^5$ ， $0≤hi,x≤1090\le h_i,x\le 10^9$ ， $1≤v≤10151\le v\le 10^{15}$ 。

思路

这种线段树上二分，维护全局信息的题目，确实常考、需要想、难调！

zc 说这是训练线段树动态开点的好题！我们发现这个倒水操作很难搞啊！

如果实时用 multiset 或（键值下标）线段树维护每个试管的体积，然后在 multiset 上二分一个均等量？就要 $O(q\log^2n)$ 了，不可搞。

于是就用权值线段树来搞，维护一段权值区间内的试管个数以及体积总数，因为 $v$ 过大不好下放，不仅不用真正修改而且还会产生精度问题。于是我们想要计算出，使尽量多的试管体积均等的体积是多少，考虑在线段树上二分答案，找一个倒水之后的均等体积 $mi d$ 。

我们不仅要找均等体积 $mi d$ ，还要找多少试管倒了水。（想可持久化线段树但失败）考虑一个二叉搜索树的结构，下标是值域，维护对应下标区间的有水银试管个数 $s i z$ 和区间水银体积和 $s u m$ 。首先单点修改很方便，主要思考查询。

像数列的指数一样将遍历过的全局信息记下来，查询时维护比 $mi d$ 小的、倒了水的水银试管个数 $C n t$ 和它们的水银体积和 $S u m$ ，以进行全局的判断。询问有 $v$ 的水，线段树上值域 $[l, r]$ 枚举到体积 $mi d$ 是合法答案，那么比 $mi d$ 小的数即左子树大小 $l s i z$ ，这些数的总和为 $l s u m$ ，考虑能否向右子树遍历：对于稍微大一点的体积 $mi d + 1$ ，需要倒：
$(Cnt+lsiz)×(mid+1)−(Sum+lsum)(Cnt+lsiz)\times(mid+1)-(Sum+lsum)$

的水（即均匀后总体积减去已有的水银体积）能均等到 $mi d + 1$ ，如果上式不大于 $v$ 就还能继续倒水，更新全局信息 $Cnt←lsiz,Sum←lsumCnt\leftarrow lsiz,Sum\leftarrow lsum$ 后遍历右子树找值域 $[mi d + 1, r]$ ，否则只能找小值域 $[l, mi d]$ 。

（感觉就是照着查询函数讲的捏，讲的冗杂了。参考了这篇博客）

ll query(ll u,ll l,ll r,ll x)`在这里插入代码片`
{if(!u)return l;//动态开点判断if(l==r){cnt+=T[u].siz;Sum+=T[u].sum;return l;}ll mid=(l+r)>>1;if((T[T[u].ls].siz+cnt)*(mid+1)-T[T[u].ls].sum-Sum>=x)return query(T[u].ls,l,mid,x);cnt+=T[T[u].ls].siz;Sum+=T[T[u].ls].sum;return query(T[u].rs,mid+1,r,x);
}

这题值域那么大，而且不太能放满值域（ $10^9$ ），因此采用动态开点节约空间。

线段树上查询的是均等体积 $e ql$ ，我们将所有试管均等后还要将剩下 $v−(eql×Cnt−Sum)v-(eql\times Cnt-Sum)$ 水，倒进 $C n t$ 个倒了水的试管里。最后再加上 $e ql$ 即答案。

注意精度问题。具体细节见代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
const ll N=1e5+9,H=1e9;
ll n,Q;
ll a[N];
ll tot;
ll cnt,Sum;
struct SegT
{struct node{ll siz;//二叉查找 ll sum;ll ls,rs;//动态开点 }T[N<<6];void modify(ll &u,ll l,ll r,ll x,ll k){if(!u)u=++tot;T[u].siz+=k;T[u].sum+=x*k;if(l==r)return;ll mid=(l+r)>>1;if(x<=mid)modify(T[u].ls,l,mid,x,k);if(x>mid)modify(T[u].rs,mid+1,r,x,k);}ll query(ll u,ll l,ll r,ll x){if(!u)return l;if(l==r){cnt+=T[u].siz;Sum+=T[u].sum;return l;}ll mid=(l+r)>>1;if((T[T[u].ls].siz+cnt)*(mid+1)-T[T[u].ls].sum-Sum>=x)return query(T[u].ls,l,mid,x);cnt+=T[T[u].ls].siz;Sum+=T[T[u].ls].sum;return query(T[u].rs,mid+1,r,x);}
}A;
ll rt;
int main()
{scanf("%lld%lld",&n,&Q);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);A.modify(rt,0,H,a[i],1);}while(Q--){ll op,x;dd v;scanf("%lld",&op);if(op==1){scanf("%lld%lf",&x,&v);A.modify(rt,0,H,a[x],-1);a[x]=v;A.modify(rt,0,H,a[x],1);}else {scanf("%lf",&v);cnt=Sum=0;ll eql=A.query(rt,0,H,v);//让试管体积均等的高度 printf("%.5lf\n",eql+(dd)(v-(eql*cnt-Sum))/(dd)cnt);}}return 0;
}

5.洛谷 P1975 排队 / P12685 排队加强版

题意

红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第 $i$ 个小朋友的身高为 $h_i$ 。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，一共交换了 $q$ 次。请你帮忙计算出每次交换后，序列的逆序对数。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的逆序对数。

$\le q \le 2\times 10^3$ ， $\le n \le 2 \times 10^4$ ， $\le h_i \le 10^9$ ， $ai≠bia_i \ne b_i$ ， $\le a_i,b_i \le n$ 。

洛谷 P12685 加强版数据： $1≤n,q≤2×1051\le n,q\le 2\times 10^5$ ，其余相同。
本篇博客将对两个数据范围进行讲解。

思路

分块是个好东西！不过平时做题，对于奇怪的区间修改以及查询、或者模某个数，都要意识到要用分块/根号分治才行！

这是机房大佬的一道数据结构题目，他要用树套树做。这个也能 cdq 分治吧，把交换询问当成时间戳搞询问么？感觉好复杂呢！先看看弱化版吧。

首先逆序对可以用归并排序（cdq 分治）、或者当成二维数点对第一维排序然后树状数组查询， $O(nlog⁡n)O(n\log n)$ 随便做，记录初始逆序对数 $ans_0$ 。因为弱化版支持 $O (n q)$ 做，对于要交换的两个下标钦定 $x < y$ ，只有下标区间在 $[x, y]$ 的逆序对的增减会影响，因此减去 $ax+1∼y−1a_{x+1\sim y-1}$ 中小于 $x$ 的和大于 $y$ 的（即少了的逆序对）、加上 $ax+1∼y−1a_{x+1\sim y-1}$ 中大于 $x$ 的和小于 $y$ 的（即多出的逆序对）。

代码1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e4+9;
ll n,Q;
ll a[N],aa[N];
ll b[N],ans;
void cdq(ll l,ll r)//归并排序求逆序对
{if(l>=r)return;ll mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);ll i=l;ll p=l,q=mid+1;while(p<=mid&&q<=r){if(a[p]<=a[q])b[i++]=a[p++];else {ans+=mid-p+1;//a[p]到a[mid]都能对a[q]贡献 b[i++]=a[q++];}}while(p<=mid)b[i++]=a[p++];while(q<=r)ans+=mid-p+1,b[i++]=a[q++];for(int o=l;o<=r;o++)a[o]=b[o];
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&aa[i]),a[i]=aa[i];cdq(1,n);printf("%lld\n",ans);scanf("%lld",&Q);while(Q--){ll x,y;scanf("%lld%lld",&x,&y);if(x>y)swap(x,y);if(aa[x]>aa[y])ans--;//aa是原数组else if(aa[x]<aa[y])ans++;//交换后形成 for(int i=x+1;i<y;i++){if(aa[i]>aa[y])ans--;else if(aa[i]<aa[y])ans++;}for(int i=x+1;i<y;i++){if(aa[i]>aa[x])ans++;else if(aa[i]<aa[x])ans--;}printf("%lld\n",ans);swap(aa[x],aa[y]);}return 0;
}

其实查询比某个数大或小的，容易用树状数组 $O(log⁡n)O(\log n)$ 求，但是这是对于全局的，对于一个区间的怎么求呢？

我们不妨把区间分成很多个部分，每个部分当做一个整体，对每个整体开一个树状数组——这是可行的，因为我们想要求的增长量，是可以每个独立部分的相加的。这不就是分块吗？（结构体树状数组优势区间）

按照分块的套路，对于同一块的直接像上面那样暴力扫，对于不同块的先处理左右残块再处理整块。最后记得修改两数所在块的树状数组（像桶一样修改就好了）以及交换两个数。

查询部分时间复杂度为 $O(q(B+nBlog⁡V))O\left(q\left(B+\dfrac{n}{B}\log V\right)\right)$ ，其中 $B$ 表示块长、 $nB\dfrac{n}{B}$ 表示块数、 $V$ 值域离散化 $a$ 数组后与 $n$ 同阶，那么 $O(q(B+nlog⁡nB))O\left(q\left(B+\dfrac{n\log n}{B}\right)\right)$ ，当 $B=nlog⁡nB=\sqrt{n\log n}$ 取得最小值。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9,B=450;
int n,Q;
int a[N];
int aa[N],nn;
ll bSize,cnt_b,bel[N],bl[B],br[B];
struct BT
{ll T[N];int lowbit(int x){return x&(-x);}void add(int x,int k){if(x==0)return;for(int i=x;i<=nn;i+=lowbit(i))T[i]+=k;}ll query(int x){ll ret=0;if(x==0)return 0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}Bt[B];
ll ans;
void init()
{bSize=sqrt(n*log2(n));cnt_b=n/bSize;if(n%bSize)cnt_b++;for(int i=1;i<=n;i++)bel[i]=(i-1)/bSize+1;for(int i=1;i<=cnt_b;i++){bl[i]=(i-1)*bSize+1;br[i]=i*bSize;}br[cnt_b]=n;for(int i=1;i<=cnt_b;i++)for(int j=bl[i];j<=br[i];j++)Bt[i].add(a[j],1);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);aa[i]=a[i];}sort(aa+1,aa+n+1);nn=unique(aa+1,aa+n+1)-aa-1;for(ll i=1;i<=n;i++)a[i]=lower_bound(aa+1,aa+nn+1,a[i])-aa;for(ll i=1;i<=n;i++){ans+=i-1-Bt[0].query(a[i]);Bt[0].add(a[i],1);}printf("%lld\n",ans);init();scanf("%d",&Q);while(Q--){ll l,r;scanf("%d%d",&l,&r);if(l>r)swap(l,r);if(a[l]<a[r])ans++;else if(a[l]>a[r])ans--;int lb=bel[l],rb=bel[r];if(lb==rb){for(int i=l+1;i<r;i++){if(a[i]>a[r])ans--;else if(a[i]<a[r])ans++;if(a[i]>a[l])ans++;else if(a[i]<a[l])ans--;}}else {for(int i=l+1;i<=br[lb];i++){if(a[i]>a[r])ans--;else if(a[i]<a[r])ans++;if(a[i]>a[l])ans++;else if(a[i]<a[l])ans--;}for(int i=bl[rb];i<r;i++){if(a[i]>a[r])ans--;else if(a[i]<a[r])ans++;if(a[i]>a[l])ans++;else if(a[i]<a[l])ans--;}for(int i=lb+1;i<rb;i++){ans-=Bt[i].query(a[l]-1);ans+=Bt[i].query(n)-Bt[i].query(a[l]);ans-=Bt[i].query(n)-Bt[i].query(a[r]);ans+=Bt[i].query(a[r]-1);}}printf("%lld\n",ans);Bt[lb].add(a[l],-1);Bt[lb].add(a[r],1);Bt[rb].add(a[r],-1);Bt[rb].add(a[l],1);swap(a[l],a[r]);}return 0;
}

6.洛谷 P4879 ycz的妹子

题意

机房神犇 ycz 有 $n$ 个青梅竹马，她们分别住在 $1 n$ 号城市中。小时候的她们美丽可爱，但是由于女大十八变，有些妹子的颜值发生了变化，但是十分重感情的 ycz 神犇不忍心抛弃她们，于是记录下来了她们颜值变化的值，我们用 $C, x, y$ 表示第 $x$ 个城市的妹子的颜值下降了 $y$ 。长大之后的 ycz 非常有魅力，有许多妹子被 ycz 迷得神魂颠倒，我们用 $I, x, y$ 表示第 $x$ 个城市有一个妹子喜欢上了 ycz ，她的颜值为 $y$ （ $y$ 有可能是负数，但是 ycz 来者不拒）。但在中途有一些妹子和 ycz 吵架了，于是就分手了，我们用 $D, x$ 表示第 $x$ 个妹子和 ycz 分手了。

最近神犇 ycz 要去全国各地找他的妹子们，为了方便计算，我们珂以把 ycz 的妹子所在的城市当作是一条直线，并且挨在一起。神犇 ycz 由于忙于和他的妹子们联系此时已经很累了，于是交给你一个这样的任务：他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度，这个愉悦度为他找的妹子的颜值数，你要做的就是求出这个愉悦度之和（注意长大后妹子们的颜值可能为负数/滑稽）。

注意：每个城市只允许有一个妹子，也就是说后来喜欢上 ycz 的妹子会赶走之前这个城市喜欢 ycz 的妹子~~（一城不容二女）~~。

UPD:

青梅竹马都是喜欢 ycz 的。

分手的第 $x$ 个妹子不是第 $x$ 城市的妹子，是指从前往后数第 $x$ 个有妹子的城市的妹子。

青梅竹马长大后就是妹子。

修改的值 $y$ 不为负数，但是颜值减去之后可能为负数。

$\le n,m \le 100000,|a_i|,|y| \le 10^9$ 。

P4879 ycz的妹子

题目背景

ycz 有很多很多的妹子（ycz：瞎说）

题目描述

注意：每个城市只允许有一个妹子，也就是说后来喜欢上 ycz 的妹子会赶走之前这个城市喜欢 ycz 的妹子~~（一城不容二女）~~。

UPD:

青梅竹马都是喜欢 ycz 的。

分手的第 $x$ 个妹子不是第 $x$ 城市的妹子，是指从前往后数第 $x$ 个有妹子的城市的妹子。

青梅竹马长大后就是妹子。

修改的值 $y$ 不为负数，但是颜值减去之后可能为负数。

ycz 有 $\times 10^5$ 座城市，开始时，前 $n$ 座城市各有一个妹子，第 $i$ 座城市妹子初始的颜值为 $a_i$ 。

有 $m$ 次以下四种操作。

C x y 第 $x$ 座城市的妹子颜值减少 $y$
I x y 第 $x$ 座城市出现了一个颜值为 $y$ 的妹子，如果在此之前，第 $x$ 座城市已经有妹子，则之前的妹子被驱赶。
D x 第 $x$ 个有妹子的城市中的妹子与 ycz 分手
Q ycz 想知道他所有妹子的颜值总和是多少

思路

被分块标签骗进来的，本来想练分块，但是发现线段树好写一些捏。

其实就是单点修改、单点赋值，不过不仅要维护区间和，因为是删去第 $x$ 个有妹子的城市，这说明如果直接把某个位置的数值抹成 $0$ 后这个位置不算一个“有妹子的城市”。

于是我们再维护区间内有 $t o t$ 个妹子，依然类比二叉查找树二分那个删除的妹子在哪里，若当前子树内要删的人 $x≤ltotx\le ltot$ 说明删除位置应在 $[l, mi d]$ 要遍历左子树；否则遍历右子树，将左子树全部跳过，在右子树内要找到第 $x - lt o t$ 个有妹子的城市。

为什么不能拿颜值为 $0$ 作为判断有没有妹子的依据呢？出现一个颜值为 $0$ 的妹子顶替，或者颜值减少到 $0$ ，就是反例。

以城市作为下标维护妹子颜值，这里值域至少要开 $2 n$ 因为询问要加人。查询部分时间复杂度 $O(qlog⁡n)O(q\log n)$

其实这里根号重构的思路也很明显了，操作数每到 $n\sqrt{n}$ 就重构？会不会很麻烦呢？

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e5+9,M=5e5+9;
ll n,Q;
ll a[N<<1];
struct SegT
{struct node{ll tot,sum;}T[M<<2];void pushup(ll u){T[u].tot=T[ls].tot+T[rs].tot;T[u].sum=T[ls].sum+T[rs].sum;}void build(ll u,ll l,ll r){if(l==r){T[u].tot=1;T[u].sum=a[l];//线段树更新的时候会出现n*2 return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void ugly(ll u,ll l,ll r,ll x,ll k){if(l==r){T[u].sum-=k;return;}ll mid=(l+r)>>1;if(x<=mid)ugly(ls,l,mid,x,k);if(x>mid)ugly(rs,mid+1,r,x,k);pushup(u);}void replace(ll u,ll l,ll r,ll x,ll k){if(l==r){T[u].tot=1;T[u].sum=k;return;}ll mid=(l+r)>>1;if(x<=mid)replace(ls,l,mid,x,k);if(x>mid)replace(rs,mid+1,r,x,k);pushup(u);}void del(ll u,ll l,ll r,ll x){if(l==r){T[u]=(node){0,0};return;}ll mid=(l+r)>>1;if(x<=T[ls].tot)del(ls,l,mid,x);else del(rs,mid+1,r,x-T[ls].tot);//子树内x-T[ls].siz个 pushup(u);}
}A;
int main()
{scanf("%lld%lld",&n,&Q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);A.build(1,1,n*2);while(Q--){char op;ll x,v;cin>>op;if(op=='Q'){printf("%lld\n",A.T[1].sum);continue;}scanf("%lld",&x);if(op=='C'){scanf("%lld",&v);A.ugly(1,1,n*2,x,v);}if(op=='I'){scanf("%lld",&v);A.replace(1,1,n*2,x,v);}if(op=='D')A.del(1,1,n*2,x);}return 0;
}

7.洛谷 P4135 作诗

题意

问题简述：给定 $n$ 个不大于 $c$ 的正整数， $a_1,a_2,...a_n$ 和 $q$ 组询问，每次问 $[l, r]$ 中有多少个数出现正偶数次。

本题强制在线。

$1≤n,c,m≤1051\le n,c,m\le 10^5$ ， $ai∈[1,c]a_i\in[1,c]$ ， $1≤l,r≤n1\le l,r\le n$ 。

思路

强制在线就不能莫队了，如果用 $log⁡\log$ 的算法也没法针对每个数（显然要 $O(qclog⁡n)O(qc\log n)$ 的吧）。于是考虑分块。

我们维护块内桶 $cnt_{i,j}$ 表示第 $i$ 块 $j$ 有多少个，前缀块桶 $xb_{i,j}$ 表示第 $1∼i1\sim i$ 块 $j$ 有多少个，虽然开区间块桶空间肯定不够，但是前缀块桶已经可以解决。

我们不难再维护 $ans_{l,r}$ 表示块 $l∼rl\sim r$ 中有多少个出现次数为正偶数的。不过这里如果枚举值域 $c$ 用前缀桶的 $O (c)$ ，显然不如利用桶的前缀性质，固定左端块每次加入右端块的贡献的 $O (B)$ 。

for(int i=1;i<=cnt_b;i++){for(int j=bl[i];j<=br[i];j++)cnt[i][a[j]]++;for(int j=0;j<=c;j++)xb[i][j]=xb[i-1][j]+cnt[i][j];}for(int l=1;l<=cnt_b;l++){for(int r=l;r<=cnt_b;r++){ans[l][r]=ans[l][r-1];for(int i=bl[r];i<=br[r];i++){tem[a[i]]++;if(tem[a[i]]%2==0)ans[l][r]++;else if(tem[a[i]]!=1)ans[l][r]--;}}for(int i=bl[l];i<=br[cnt_b];i++)tem[a[i]]--;}

考虑查询，依然是分块套路，同块暴扫；不同块就先处理残块。因为我们预处理可以得到块 $lb+1∼rb−1lb+1\sim rb-1$ 的答案 $ans_{lb+1,rb-1}$ ，然后用一个临时桶、再加上前缀桶处理每个答案的增删。变成奇数就 $- 1$ （ $1$ 除外，因为个数为 $0$ 没有统计）、偶数就 $+ 1$ 。

ret=ans[lb+1][rb-1];
for(int i=l;i<=br[lb];i++)
{ll t=++tem[a[i]];ll tot=xb[rb-1][a[i]]-xb[lb][a[i]]+t;if(tot%2==0)ret++;else if(tot!=1)ret--;
}
for(int i=bl[rb];i<=r;i++)
{ll t=++tem[a[i]];ll tot=xb[rb-1][a[i]]-xb[lb][a[i]]+t;if(tot%2==0)ret++;else if(tot!=1)ret--;
}
for(int i=l;i<=br[lb];i++)
tem[a[i]]--;
for(int i=bl[rb];i<=r;i++)
tem[a[i]]--;//还原临时桶

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9,B=319;
ll n,c,Q;
ll a[N];
ll bSize,cnt_b,bel[N],bl[N],br[N];
ll cnt[B][N],xb[B][N],ans[B][B];
ll tem[N];
bool vis[N];
void init()
{bSize=sqrt(n);cnt_b=n/bSize;if(n%bSize)cnt_b++;for(int i=1;i<=n;i++)bel[i]=(i-1)/bSize+1;for(int i=1;i<=cnt_b;i++){bl[i]=(i-1)*bSize+1;br[i]=i*bSize;}br[cnt_b]=n;for(int i=1;i<=cnt_b;i++){for(int j=bl[i];j<=br[i];j++)cnt[i][a[j]]++;for(int j=0;j<=c;j++)xb[i][j]=xb[i-1][j]+cnt[i][j];}for(int l=1;l<=cnt_b;l++){for(int r=l;r<=cnt_b;r++){ans[l][r]=ans[l][r-1];for(int i=bl[r];i<=br[r];i++){tem[a[i]]++;if(tem[a[i]]%2==0)ans[l][r]++;else if(tem[a[i]]!=1)ans[l][r]--;}}for(int i=bl[l];i<=br[cnt_b];i++)tem[a[i]]--;}
}
ll query(ll l,ll r)
{ll lb=bel[l],rb=bel[r],ret=0;if(lb==rb){for(int i=l;i<=r;i++)tem[a[i]]++;for(int i=l;i<=r;i++){if(!vis[a[i]]&&tem[a[i]]%2==0)ret++;vis[a[i]]=1;}for(int i=l;i<=r;i++)tem[a[i]]=0,vis[a[i]]=0;return ret;}ret=ans[lb+1][rb-1];for(int i=l;i<=br[lb];i++){ll t=++tem[a[i]];ll tot=xb[rb-1][a[i]]-xb[lb][a[i]]+t;if(tot%2==0)ret++;else if(tot!=1)ret--;}for(int i=bl[rb];i<=r;i++){ll t=++tem[a[i]];ll tot=xb[rb-1][a[i]]-xb[lb][a[i]]+t;if(tot%2==0)ret++;else if(tot!=1)ret--;}for(int i=l;i<=br[lb];i++)tem[a[i]]--;for(int i=bl[rb];i<=r;i++)tem[a[i]]--;return ret;
}
int main()
{scanf("%lld%lld%lld",&n,&c,&Q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);init();ll lans=0;while(Q--){ll l,r;scanf("%lld%lld",&l,&r);l=(l+lans)%n+1,r=(r+lans)%n+1;if(l>r)swap(l,r);lans=query(l,r);printf("%lld\n",lans);}return 0;
}