首页 > 其他分享 >P10149 [Ynoi1999] XM66F 题解

P10149 [Ynoi1999] XM66F 题解

时间:2024-03-05 19:00:10浏览次数:30  
标签:Cnt int 题解 sum XM66F ans P10149 id define

分析

考虑莫队。

对于 $a_i=k(l \le i \le r)$ 的下标集合 $S_k$,当其加入一个新的下标 $x$ 时,这个新下标对答案的贡献分两种情况。

第一种,$x$ 最小。相邻从下标的间隔中产生的贡献是 $\sum (|S_k|-i+1)\times(ans_{S_{k,i+1}}-ans_{S_{k,i}})$。画个图可以理解一下:

第二中,$x$ 最大。相邻从下标的间隔中产生的贡献是 $\sum i\times(ans_{S_{k,i+1}}-ans_{S_{k,i}})$。画个图可以理解一下:

其中绿色部分是产生的贡献,$ans_i$ 表示前 $i$ 个数中小于 $a_i$ 的数量。

然后就是把上面的情况在莫队里 $O(1)$ 更新。很简单,考虑前缀和优化。定义 $s_i = \sum\limits_{j=1\land S_{a_i,j} \le i}^{|S_{a_i}|} ans_{S_{a_i,j}}$。

第一种情况有 $\sum (|S_k|-i+1)\times(ans_{S_{k,i+1}}-ans_{S_{k,i}})=s_{S_{k,|S_k|}}-s_{S_{k,1}}-(|S_k|-1) \times ans_{S_{k,1}}$。其实就是找到当前区间的区间和在减掉多出算的。画个图可以理解一下:

橙色部分是前缀和,需要保留 $3$ 部分,第一次减掉 $1$ 部分,第二次减掉 $2$ 部分。

第二种情况同理,可以自己推一下。

复杂度 $O(n \log n +n\sqrt{n})$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	il auto max(auto a,auto b){return (a>b?a:b);}
	il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=5e5+10;
int n,m,a[N],w[N];
struct Query{
	int l,r,id;
}Q[N];
int len,sum,ans[N];
vector<int> x[N];
int s[N];
int cnt[N],Cnt[N];
int tr[N],pre[N],nxt[N],lst[N];
int L[N],R[N];

il void add(int x){
	while(x<=n) ++tr[x],x+=x&(-x);
}
il int query(int x){
	int ans=0;
	while(x) ans+=tr[x],x-=x&(-x);
	return ans;
}
il bool cmp(Query a,Query b){
	if(a.l/len!=b.l/len) return a.l<b.l;
	if((a.l/len)&1) return a.r<b.r;
	return a.r>b.r;
}
il void Add(int id,int f){
	int x=a[id];
	++Cnt[x];
	if(Cnt[x]==1) return L[x]=R[x]=id,void(0);
	if(f==1){
		L[x]=id;
		sum+=s[R[x]]-s[L[x]]-(Cnt[x]-1)*cnt[id];
	}
	else{
		R[x]=id;
		sum+=s[pre[L[x]]]+(Cnt[x]-1)*cnt[id]-s[pre[R[x]]];
	}
	return ;
}
il void Del(int id,int f){
	int x=a[id];
	--Cnt[x];
	if(Cnt[x]==0) return L[x]=R[x]=0,void(0);
	if(f==1){
		sum-=s[R[x]]-s[L[x]]-Cnt[x]*cnt[id];
		L[x]=nxt[id];
	}
	else{
		sum-=s[pre[L[x]]]+Cnt[x]*cnt[id]-s[pre[R[x]]];
		R[x]=pre[id];
	}
	return ;
}

il void solve(){
	n=rd,m=rd,len=sqrt(n);
	for(re int i=1;i<=n;++i) x[i].push_back(0);
	for(re int i=1;i<=n;++i) a[i]=rd,x[a[i]].push_back(i),w[i]=x[a[i]].size();
	for(re int i=1;i<=m;++i) Q[i]={rd,rd,i};
	sort(Q+1,Q+m+1,cmp);
	
	for(re int i=1;i<=n;++i) cnt[i]=query(a[i]-1),add(a[i]);
	for(re int i=1;i<=n;++i){
		s[i]=cnt[i]+s[lst[a[i]]];
		nxt[lst[a[i]]]=i,pre[i]=lst[a[i]],lst[a[i]]=i;
	}
	
	int l=1,r=0;
	for(re int i=1;i<=m;++i){
		while(l>Q[i].l) Add(--l,1);
		while(r<Q[i].r) Add(++r,2);
		while(l<Q[i].l) Del(l++,1);
		while(r>Q[i].r) Del(r--,2);
		ans[Q[i].id]=sum;
	}
	for(re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int t=1;while(t--)
	solve();
	return 0;
} 

标签:Cnt,int,题解,sum,XM66F,ans,P10149,id,define
From: https://www.cnblogs.com/harmisyz/p/18054667

相关文章

  • AT_abc343_G [ABC343G] Compress Strings 题解
    分析水题,评分能有$2100$可能是因为很多人卡E了。我说真的,E好难啊。$n$只有$20$,考虑从状压的角度入手。定义状态函数$f_{s,i}$表示当某个字符串$T$包含了所有$s$的二进制中为$1$的下标$S_j$且$T$末尾包含的子串为$S_i$时$T$的最小长度。那很显然的就有转......
  • 题解:卡农(组合计数+DP)
    题面题目链接简化一下,有\(3\)个限制:不能是空集。每个元素出现的次数必须为偶数。不能出现两个相同的集。思路首先不用状压,但是需要\(DP\),因为\(n\)范围过大用状压内存放不下,不然本来状压很好用的。考虑数学方法\(+DP\)。限制\(1\)因为不能有空集,所以可选......
  • tomcat8.5+ windows中html页面及控制台中文乱码问题解决办法
    tomcat8.5+windows中html页面及控制台中文乱码问题解决办法————————————————版权声明:本文为博主原创文章,遵循CC4.0BY-SA版权协议,转载请附上原文出处链接和本声明。原文链接:https://blog.csdn.net/onemy/article/details/106215384 https://blog.csdn.......
  • 题解 P10220【[省选联考 2024] 迷宫守卫】
    \(\text{Link}\)葬送了我2024省选的一题。题意有一颗深度为\(n+1\)的完全二叉树,其叶子上依次标有一个长为\(2^n\)排列\(a\),非叶结点有选择代价\(b_i\)。Alice、Bob两人进行游戏。Alice可以选择一些选择代价和不超过\(m\)的非叶结点,此后Bob会从根开始深度优先搜索......
  • 2024-selenium-问题一:java.io.IOException: Invalid Status code=403 text=Forbidden
    问题截图:  问题分析: 参考网址:https://blog.csdn.net/weixin_46739493/article/details/134163739问题解决:1、chrome版本为:版本114.0.5735.199(正式版本);driver的版本为:114.0.5735.90; java-seleium版本为:4.0.0-rc-21<dependency>2<groupId>org.......
  • [省选联考 2024] 题解
    D1T1P10217季风题意有点抽象,大概就是要求我们对两个有若干次重复的序列进行操作,每次可以将这两个序列都向上或向下调整一个值,但是调整的绝对值的总和有限制,问能否最终将总和调整至固定值。由于\(m\)不一定是\(n\)的倍数,因此序列在重复若干次之后可能会遗留一些散块,这是不......
  • P10217 [省选联考 2024] 季风 题解
    [省选联考2024]季风Description给定\(n,k,x,y\)和\(2n\)个整数\(x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}\)。找到最小的非负整数\(m\),使得存在\(2m\)个实数\(x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'\)满足以下条件,或报告不存在这样的\(m\):\(\s......
  • Luogu P1220 关路灯 题解 [ 蓝 ][ 区间dp ]
    关路灯题目描述某一村庄在一条路线上安装了\(n\)盏路灯,每盏灯的功率有大有小(即同一段时间内消耗的电量有多有少)。老张就住在这条路中间某一路灯旁,他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费,老张记录下了每盏路灯的位置和功率,他每次关......
  • abc343G 题解
    题意给你\(N\)个由小写字母组成的字符串\(S_1,S_2,\ldots,S_N\),找出一个母串使得它包含所有这些字符串作为它的子串,最小化该母串的长度并输出。\(1\leqN\leq20\),\(\sum|S_i|\leq2\times10^5\)(没错洛谷翻译就是我写的)思路首先如果有一个字符串被另一个字符串......
  • P10220 [省选联考 2024] 迷宫守卫 题解
    说一下自己赛时做法。赛时会了,但没能调出来,几乎确定进不去队了,留下这篇题解作为这次比赛的记录吧。称激活守卫为打开开关。首先考虑,如果确定所有开关的情况,Bob有一个简单的贪心做法:当走到一个点时,递归其左右子树并得到两个序列,若右子树的对应序列的小于左子树的对应序列,则右边......