首页 > 其他分享 >P10833 [COTS 2023] 下 Niz题解

P10833 [COTS 2023] 下 Niz题解

时间:2024-11-13 16:29:45浏览次数:1  
标签:node le int 题解 Niz lst 排列 2023 区间

题意:
给定长度为 \(N\) 的序列 \(a\),求满足以下条件的 \((l,r)\) 对数:

  • \(1\le l\le r\le N\);

  • \(a_l,a_{l+1},\cdots,a_{r-1},a_r\) 是 \(1\sim r-l+1\) 的排列。

  • \(1\le N\le 10^6\);\(1\le a_i\le N\)。

思路

  • 首先,“排列”本身这个性质是很强的。因为排列本身需要从1开始,因此排列的数目必定不会很多。
    同时,只要我们知道了排列中最大的数,我们就知道了这个排列的长度。

  • 因此考虑去找区间中最大的数,然后去枚举区间的范围。在这个区间中,我们其实就将问题转化为了区间内的数的种类。只不过这里种类必须为区间长度。
    这种问题有一个很经典的转化,即维护一个数上一个与其值相同的数出现的位置,然后线段树去统计。
    不过这道题并不需要,因为我们只需要判断种类数是不是 \(n\) 就行了,因此可以用st表 \(O(1)\) 判断,只需要区间内所有数上一次出现的位置都小于区间左端点就行了。

  • 处理完最大值后就可以继续向两边递归去找。

复杂度

  • 这里的时间复杂度与启发式合并比较类似,平摊下来总体是 \(O(nlogn)\) 的。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N],g[N][20],lst[N],lg[20];long long ans=0;
struct node
{
	int val,loc;
}f[N][20];
node maxx(node x,node y){return x.val>=y.val?x:y;}
void init()
{
	lg[0]=-1;for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
	for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)
	f[j][i]=maxx(f[j][i-1],f[j+(1<<(i-1))][i-1]),g[j][i]=max(g[j][i-1],g[j+(1<<(i-1))][i-1]);
}
node fmax(int l,int r){int x=lg[r-l+1];return maxx(f[l][x],f[r-(1<<x)+1][x]);}
int  gmax(int l,int r){int x=lg[r-l+1];return max (g[l][x],g[r-(1<<x)+1][x]);}
bool query(int l,int r){return gmax(l,r)<l;}
void solve(int l,int r)
{
	if(r<l) return;if(l==r) {ans+=(a[l]==1);return;}
	node mval=fmax(l,r);
	if(mval.loc-l<=r-mval.loc) 
	for(int i=max(l,mval.loc-mval.val+1),j=i+mval.val-1;i<=mval.loc&&j<=min(r,mval.loc+mval.val-1);++i,++j) ans+=query(i,j);
	else for(int j=mval.loc,i=j-mval.val+1;i<=mval.loc,j<=min(r,mval.loc+mval.val-1);++i,++j) if(i<l) continue;else ans+=query(i,j);
	solve(l,mval.loc-1),solve(mval.loc+1,r);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];f[i][0]={a[i],i},g[i][0]=lst[a[i]],lst[a[i]]=i;}
	init();solve(1,n);cout<<ans<<'\n';
	return 0;
}

标签:node,le,int,题解,Niz,lst,排列,2023,区间
From: https://www.cnblogs.com/allforgod/p/18544283

相关文章

  • AT_agc011_d [AGC011D] Half Reflector 题解
    用\(1\)表示A,\(0\)表示B,观察进行一次操作后字符串会发生什么变化。首先当第一个数为\(1\)时,只会将第一个数变为\(0\)。对于剩下的情况,手玩一下可以发现会将第一个数移到末尾,然后将所有数异或\(1\)。先考虑暴力怎么做,可以记一个指针\(i\)和当前应该给全体数异或的值\(......
  • P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解
    题意:给定一个长度为\(n=2^k\)的数组\(a\),下标从\(0\)开始,维护\(m\)次操作:给定\(x\),设数列\(a'\)满足\(a'_i=a_{i\oplusx}\),将\(a\)修改为\(a'\)。其中\(\oplus\)表示按位异或运算。给定\(l,r\),查询\(a\)的下标在\(l,r\)之间的子数组有多少颜色段。不保......
  • [题解]P3225 [HNOI2012] 矿场搭建
    P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解,我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”,“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图,橙色点是割点,红色框圈出的是点双,加粗的是叶子连通......
  • P2612 [ZJOI2012] 波浪 题解
    前置知识:连续段dp题目链接:P2612[ZJOI2012]波浪随机一个\(1\)到\(n\)的排列\(P_{1...n}\),问以下式子的值\(\lem\)的概率是多少?\[|P_1-P_2|+|P_2-P_3|+|P_3-P_4|+...+|P_{n-1}+P_n|\]输出一个答案表示概率。保留\(k\)位小数。对于\(40%\)......
  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......
  • Codeforces Round 985 div1+2 个人题解(A~E)
    CodeforcesRound985div1+2个人题解(A~E)Dashboard-Refact.aiMatch1(CodeforcesRound985)-Codeforces火车头#include<bits/stdc++.h>usingnamespacestd;#defineftfirst#definesdsecond#defineyescout<<"yes\n"#definenoc......
  • [CF1935E] Distance Learning Courses in MAC 题解
    [CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话,因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数,使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\),且越是高......
  • [USACO06NOV] Corn Fields G 题解
    题目链接[USACO06NOV]CornFieldsG题解这是一道典型的状压dp,对于\(M\)行\(N\)列的图,由于每个点只有\(1\)和\(0\)两种状态,我们将其压缩为一个长度为\(M\)的数组,数组(\(g\))的每一项\(g_{i}\)表示状态的二进制表示法表示的数(如\(101\)表示为\(5\)),我们预先处......
  • [CEOI2023] A Light Inconvenience 题解
    Description今年CEOI的开幕式上有一场精彩的火炬表演。表演者们站成一排,从\(1\)开始从左往右编号。每个表演者举着一根火炬,初始只有一个举着点燃的火炬的表演者。表演分为\(Q\)幕。在第\(a\)幕开始之前,要么\(p_a>0\)个表演者从右侧加入表演,他们的火炬是熄灭的;要么最......