首页 > 其他分享 >luogu P8275 [USACO22OPEN] 262144 Revisited P

luogu P8275 [USACO22OPEN] 262144 Revisited P

时间:2022-10-24 17:44:48浏览次数:123  
标签:int luogu P8275 合并 Ts using Revisited size define

题面传送门

这里有个sb写这道题写了一下午。

首先来考虑一段子段上的答案,显然答案有一个区间,设最大值为\(E\),则最小值一定在\([E,E+\log n]\)之间。

我们考虑按照最大值分段,最优秀的状态应该是最后合并成若干个\(E\),然后直接对这些\(E\)归并起来就是答案,但是最大值分出来的段可能不是这么凑巧,但是实际上如果合并不出来\(E\)可以当成一个\(E\)来看,因为最优秀的合并一定不会有两个不是\(E\)的相邻,而这样的话在合并时和\(E\)没什么区别。

这样我们基本上可以得到一个策略,先按照最大值分段,然后每段内计算出合并成\(E\)的最少的数量,设总个数为\(p\),则这个子段的答案为\(\lceil \log p\rceil\)。

建立笛卡尔树,然后对这个过程分治。每次从孩子节点合并出左子树和右子树合并成啥样,然后再根据当前的权值进行进一步合并。

然后是统计答案,我们枚举答案和\(E\)的增量,然后统计答案至少为\(E+\delta\)的区间个数,这样也可以得到权值和。枚举这个权值后可以枚举较小一边的点,然后去计算有多少个右端点合法即可。

但你实际上写出来会有一点问题。

1.在合并某个子树内的值的时候,因为总删除次数只有\(n\)次,因此直接暴力删即可。

2.在统计答案的时候,我们取的最小值其实不是两个待合并的最小值,而是分开来的最小值,因此不能简单地用启发式合并的方式证明复杂度。但是我们注意到它们对应的原序列上的长度是相同的,而对原序列启发式合并的复杂度是\(O(n\log n)\),因此这个低于原序列合并复杂度。可以认为是\(O(n\log^2n)\)的。

3.在合并左右子树的时候发现合并不能改变相对顺序。因此简单的vector无法解决。我们考虑用这样的一种方式合并:

初始化vector具有\(x\)个空位与在此之后的\(x\)个值。每次合并,如果后面的大小小于前面的,那么直接将后面的合并到前面即可。如果前面的小于后面的,那么就将前面的值填入后面的空位中,如果空位不足直接重构。

后面一部分发现如果重构那么大小至少变成两倍,因此总复杂度\(O(n\log n)\),且可以\(O(1)\)查询。

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=(1<<18)+5,M=N*4+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=2e9+7;const db eps=1e-5;
int n,A[N],L[N],R[N],st[N],H,Rt,lg[N*2],Si[N],Ph;ll Ans;
struct Node{int x,w,id;Node operator +(const Node &B)const{return (Node){max(x,B.x)+1,w+B.w,id};};}Cl,P[N];
#define CL(A) A.clear(),A.shrink_to_fit()
struct Ques{
	vector<Node> Ts;int H;Node find(int x){return x+H>=Ts.size()?Cl:Ts[x+H];}
	void CG(int w){
		while(Ts.size()-H>1&&max(Ts[H].x,Ts[H+1].x)<w) {Ph=-1;for(int i=H;i<Ts.size();i++) (i-H)&1?(P[Ph]=P[Ph]+Ts[i]):(P[++Ph]=Ts[i]);
			CL(Ts);for(int i=0;i<=Ph;i++) Ts.PB(Cl);for(int i=0;i<=Ph;i++) Ts.PB(P[i]);H=Ph+1;
		}
	}
	void Mg(Ques &B){ 
		if(Ts.size()-H>B.Ts.size()-B.H) {for(int i=B.H;i<B.Ts.size();i++) Ts.PB(B.Ts[i]);CL(B.Ts);return;}
		if(Ts.size()-H<=B.H){for(int i=Ts.size()-1;i>=H;i--) B.Ts[--B.H]=Ts[i];swap(B.Ts,Ts);H=B.H;CL(B.Ts);return;}
		int i;Ph=-1;for(i=H;i<Ts.size();i++) P[++Ph]=Ts[i];for(i=B.H;i<B.Ts.size();i++) P[++Ph]=B.Ts[i];CL(Ts);for(i=0;i<=Ph;i++) Ts.PB(Cl);for(i=0;i<=Ph;i++) Ts.PB(P[i]);CL(B.Ts);H=Ph+1;
	}
}S1[N],S2[N];
void dfs(int x){if(!x) return;dfs(L[x]);dfs(R[x]);int i,j;Si[x]=Si[L[x]]+Si[R[x]]+1;S1[L[x]].CG(A[x]);S1[R[x]].CG(A[x]);S2[L[x]].CG(A[x]);S2[R[x]].CG(A[x]);
	S1[x].Ts.PB((Node){A[x],1,x});S2[x].Ts.PB((Node){A[x],1,x});
	S1[x].Mg(S1[R[x]]);S1[R[x]]=S1[0];S2[x].Mg(S2[L[x]]);S2[L[x]]=S2[0];
	Ans+=1ll*(Si[L[x]]+1)*(Si[R[x]]+1)*A[x];
	//cerr<<x<<' '<<Ans<<'\n';for(Node p:S1[x]) cerr<<p.w<<' ';cerr<<'\n';for(Node p:S2[x]) cerr<<p.w<<' ';cerr<<'\n'; 
	for(i=0;i<=lg[S1[x].Ts.size()+S2[x].Ts.size()-S1[x].H-S2[x].H];/*cerr<<Ans<<'\n',*/i++) {
		if(S1[x].Ts.size()-S1[x].H<S2[x].Ts.size()-S2[x].H)for(j=0;j<S1[x].Ts.size()-S1[x].H;j++) Ans+=1ll*S1[x].find(j).w*(max((1<<i)-j,0)+S2[x].H>=S2[x].Ts.size()?0:S2[x].find(max(0,(1<<i)-j)).id-(x-Si[L[x]])+1)/*,cerr<<S2[x].find(max(0,(1<<i)-j)).id<<' '<<x-Si[L[x]]<<' '<<Ans<<'\n'*/;
		else for(j=0;j<S2[x].Ts.size()-S2[x].H;j++) Ans+=1ll*S2[x].find(j).w*(max((1<<i)-j,0)+S1[x].H>=S1[x].Ts.size()?0:x+Si[R[x]]+1-S1[x].find(max(0,(1<<i)-j)).id);
	}
	
//	for(Node i:S1[x]) S1[L[x]].PB(i);swap(S1[L[x]],S1[x]);S1[L[x]].clear();S1[L[x]].shrink_to_fit();for(Node i:S2[x]) S2[R[x]].PB(i);swap(S2[R[x]],S2[x]);S2[R[x]].clear();S2[R[x]].shrink_to_fit();
	S1[L[x]].Mg(S1[x]);swap(S1[L[x]],S1[x]);S1[L[x]]=S1[n+1];S2[R[x]].Mg(S2[x]);swap(S2[R[x]],S2[x]);S2[R[x]]=S2[n+1];if(x%100==0) cerr<<x<<'\n';
}
int main(){
	freopen("1.in","r",stdin);
	int i;scanf("%d",&n);A[0]=1e9;for(i=1;i<=n;i++){scanf("%d",&A[i]);while(A[st[H]]<A[i]) H--;L[i]=R[st[H]];R[st[H]]=i;st[++H]=i;}Rt=R[0];
	for(i=2;i<=2*n+1;i++) lg[i]=((1<<lg[i-1])==i-1?lg[i-1]+1:lg[i-1]);dfs(Rt);printf("%lld\n",Ans); 
} 

标签:int,luogu,P8275,合并,Ts,using,Revisited,size,define
From: https://www.cnblogs.com/275307894a/p/16821941.html

相关文章

  • luogu P8585 球状精灵的传说 题解
    题目大意给定\(n\)个精灵的三维幅度\(\{r_{1,i},r_{2,i},r_{3,i}\}\),任意两个精灵若在三个幅度中有两个相同(这里可以乱序)则可以将剩下的一位相加组合起来。组合过的精......
  • Luogu P8348
    构造题。……这玩意儿怎么构造。不过只用判断Yes/No。考虑找一个方法唯一的表示一对数能表示的拓展出的序列包含的所有“一对数”。容易想到一直减到最小,用最终结果......
  • [luogu6575]Friends
    记$s=p+q$,当存在一个点度数$\ges$时,显然无解记$d_{S,T}=\sum_{x\inS,y\inT}[(x,y)\inE]$,称$S\subseteqV$合法当且仅当$|S|\lep$且$d(S,V\backslashS)\leq$结论:若......
  • Luogu P2656采蘑菇(Tarjan + spfa)
    采蘑菇题目描述小胖和ZYR要去ESQMS森林采蘑菇。ESQMS森林间有\(N\)个小树丛,\(M\)条小径,每条小径都是单向的,连接两个小树丛,上面都有一定数量的蘑菇。小胖和ZYR......
  • 【luogu AGC034F】RNG and XOR(FWT)
    RNGandXOR题目链接:luoguAGC034F题目大意给你一个长度为2^n的数组A。一开始有一个\(0\)数,然后每次你随机给它异或上0~2^n-1中的数,随机到\(i\)的概率跟Ai+1......
  • luogu P1972 SDOI2009 HH的项链
    P1972SDOI2009HH的项链-洛谷|计算机科学教育新生态(luogu.com.cn)维护一个长度同为\(n\)的数组\(b\)。一个指针\(R\)从\(1\)扫到\(n\)并做如下操作:检查......
  • 【luogu CF1163F】Indecisive Taxi Fee(图论)(分类讨论)
    IndecisiveTaxiFee题目链接:luoguCF1163F题目大意给你一个无向图,每次改一条边的权值(每次都会变回来),问你1~n的最短路长度。思路考虑分类讨论,先找到最短路的路径,然......
  • 【luogu CF1140F】Extending Set of Points(线段树分治)
    ExtendingSetofPoints题目链接:luoguCF1140F题目大意有一个点集,有一个扩展操作是加入符合条件的(x0,y0)直到不能加入位置。符合条件是原来(x0,y0)不存在而且存......
  • luogu P3685 [CERC2016]不可见的整数 Invisible Integers
    题面传送门真的吐了,写了五六个小时。首先我们不考虑两边都能走,只考虑向左走,那么的话如果两个从左到右的集合分别为\(S1,S2\),则\(S1\subsetS2\),且除去\(S1\)已经匹配掉的......
  • luogu P5339 [TJOI2019]唱、跳、rap和篮球 (容斥,指数型母函数,NTT)
    https://www.luogu.com.cn/problem/P5339要求不含1234的方案,反过来求含至少一个1234的方案。钦定存在i个位置有1234,位置的方案是Cn-3i,i.其他n-4i个位置的方案是多重集......