首页 > 其他分享 >CF1585F. Non-equal Neighbours

CF1585F. Non-equal Neighbours

时间:2023-05-29 21:22:38浏览次数:44  
标签:Non return int sum Tr CF1585F add Neighbours mod

三倍经验:CF1591F. Non-equal NeighboursARC115E - LEQ and NEQ

提供一种力大砖飞的数据结构 \(O(n\log n)\) 做法,非常好写/好调,去掉数据结构部分只有 1k。

定义 \(f_{i,j}\) 表示前 \(i\) 个数,最后一个为 \(j\) 的方案数。显然第 1 维可以压掉,写成 \(f_j\) 的形式。

然后这个东西可以前缀和做到 \(O(\sum a)\)。更具体地说,对于前 \(i-1\) 个数,定义 \(s=\sum\limits_{k=1}^{a_{i-1}}f_k\),加上第 \(i\) 个数之后有 \(f_k=s-f_k\)。这个东西似乎不能优化了。

但是,我们可以发现,对于很多连续的 \(f_k\),他们的值是一样的:对于 \(a_i\ge a_{i-1}\),由于原来从 \(a_{i-1}+1\) 到 \(a_i\) 的这些位置都没有值,所以相当于在最后插入了值为 \(s\) 的一段;对于 \(a_i<a_{i-1}\),相当于舍弃后面一部分 dp 值。

当然,每次剩余的那些段都会把值从 \(v_i\) 变成 \(s-v_i\),但这并不影响。

每次最多加入一段,所以最多 \(n\) 段;每段最多加一次删一次,故时间复杂度 \(O(n\log n)\)。那个 \(\log n\) 是用线段树维护每段具体值的时间。

code:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18,mod=998244353;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int a[500005];
struct Node{
	int l,r;
}q[500005];
struct segtree{
	#define ls p<<1
	#define rs p<<1|1
	#define lson l,mid,ls
	#define rson mid+1,r,rs
	struct Node{
		int s,add,mul;
	}c[2000005];
	void pushup(int p){
		c[p].s=(c[ls].s+c[rs].s+mod)%mod;
	}
	void pushdown(int l,int r,int p){
		if(c[p].mul!=1){
			c[ls].s=(c[ls].s*c[p].mul%mod+mod)%mod;
			c[rs].s=(c[rs].s*c[p].mul%mod+mod)%mod;
			c[ls].add=(c[ls].add*c[p].mul%mod+mod)%mod;
			c[rs].add=(c[rs].add*c[p].mul%mod+mod)%mod;
			c[ls].mul=(c[ls].mul*c[p].mul%mod+mod)%mod;
			c[rs].mul=(c[rs].mul*c[p].mul%mod+mod)%mod;
			c[p].mul=1;
		}
		if(c[p].add!=0){
			int siz=r-l+1,ln=siz-(siz>>1),rn=siz>>1;
			c[ls].s=(c[ls].s+ln*c[p].add%mod+mod)%mod;
			c[rs].s=(c[rs].s+rn*c[p].add%mod+mod)%mod;
			c[ls].add=(c[ls].add+c[p].add+mod)%mod;
			c[rs].add=(c[rs].add+c[p].add+mod)%mod;
			c[p].add=0;			
		}
	}
	void build(int l,int r,int p){
		c[p].add=0;
		c[p].mul=1;
		if(l==r){
			c[p].s=0;
			return;
		}
		int mid=(l+r)>>1;
		build(lson);
		build(rson);
		pushup(p);
	}
	void mul(int l,int r,int p,int L,int R,int k){
		if(L>R)return;
		if(L<=l&&r<=R){
			c[p].s=(c[p].s*k%mod+mod)%mod;
			c[p].add=(c[p].add*k%mod+mod)%mod;
			c[p].mul=(c[p].mul*k%mod+mod)%mod;
			return;
		}
		int mid=(l+r)>>1;pushdown(l,r,p);
		if(L<=mid)mul(lson,L,R,k);
		if(R>mid)mul(rson,L,R,k);
		pushup(p);
	}
	void add(int l,int r,int p,int L,int R,int k){
		if(L>R)return;
		if(L<=l&&r<=R){
			c[p].s=(c[p].s+(r-l+1)*k%mod+mod)%mod;
			c[p].add=(c[p].add+k+mod)%mod;
			return;
		}
		int mid=(l+r)>>1;pushdown(l,r,p);
		if(L<=mid)add(lson,L,R,k);
		if(R>mid)add(rson,L,R,k);
		pushup(p);
	}
	int query(int l,int r,int p,int L,int R){
		if(L>R)return 0;
		if(L<=l&&r<=R)return c[p].s;
		int mid=(l+r)>>1,res=0;pushdown(l,r,p);
		if(L<=mid)res=(res+query(lson,L,R)+mod)%mod;
		if(R>mid)res=(res+query(rson,L,R)+mod)%mod;
		return res;
	}
	#undef ls 
	#undef rs
	#undef lson
	#undef rson
}Tr;
void solve(){
	int n=read(),L=1,R=0,sum=0;
	for(int i=1;i<=n;i++)a[i]=read();
	Tr.build(1,n,1);
	q[++R]=(Node){1,a[1]},sum=(sum+a[1])%mod;
	Tr.mul(1,n,1,R,R,0);Tr.add(1,n,1,R,R,1);
	for(int i=2;i<=n;i++){
		if(a[i]>=a[i-1]){
			Tr.mul(1,n,1,L,R,-1);Tr.add(1,n,1,L,R,sum);
			q[++R]=(Node){a[i-1]+1,a[i]};
			Tr.mul(1,n,1,R,R,0);Tr.add(1,n,1,R,R,sum);
			sum=(sum*a[i]%mod-sum+mod)%mod;
		}
		else{
			int nsum=sum;
			while(L<=R&&q[R].l>a[i])nsum=(nsum-Tr.query(1,n,1,R,R)*(q[R].r-q[R].l+1)%mod+mod)%mod,R--;
			if(L<=R&&q[R].r>a[i])nsum=(nsum-Tr.query(1,n,1,R,R)*(q[R].r-a[i])%mod+mod)%mod,q[R].r=a[i];
			Tr.mul(1,n,1,L,R,-1);Tr.add(1,n,1,L,R,sum);
			sum=(sum*a[i]%mod-nsum+mod)%mod;	
		}
	}
	printf("%lld\n",sum);
}
signed main(){
	int T=1;
	while(T--)solve();
	return 0;
}

标签:Non,return,int,sum,Tr,CF1585F,add,Neighbours,mod
From: https://www.cnblogs.com/xx019/p/17441664.html

相关文章

  • com.alibaba.fastjson.JSONException: can‘t create non-static inner class inst
    在类修饰符前面加上static即可 ......
  • java8 stream匹配 anyMatch,allMatch,noneMatch
    anyMatch:判断的条件里,任意一个元素成功,返回trueallMatch:判断条件里的元素,所有的都是,返回truenoneMatch:与allMatch相反,判断条件里的元素,所有的都不是,返回truecount方法,跟List接口中的.size()一样,返回的都是这个集合流的元素的长度,不同的是,流是集合的一个高级工厂,中间操作是工厂里......
  • Python默认编码错误SyntaxError: Non-ASCII character '\xe5'之解决方法
    在编写Python时,当使用中文输出或注释时运行脚本,会提示错误信息:解决方法:python的默认编码文件是用的ASCII码,你将文件存成了UTF-8!!!(文件中存在中文或者其他语言,就会出现此问题!)解决办法很简单!!!在文件开头加入:# -*- coding: U......
  • Java自定义注解(Annontation)
    (一)注解简介注解(Annontation),Java5引入的新特性,位于java.lang.annotation包中。提供了一种安全的类似注释的机制,用来将任何的信息或元数据(metadata)与程序元素(类、方法、成员变量等)进行关联。是一种说明、配置、描述性的信息,与具体业务无关,也不会影响正常的业务逻辑。但我们可以用反......
  • CAfile: /etc/ssl/certs/ca-certificates.crt CApath: none
    报错信息:cURLerror77:errorsettingcertificateverifylocations: CAfile:/etc/ssl/certs/ca-certificates.crtCApath:none  ln-s/etc/pki/ca-trust/extracted/openssl/ca-bundle.trust.crt/etc/ssl/certs/ca-certificates.crt......
  • 报错:TypeError: Found non-callable @@iterator
    代码://自动导入插件constautpImport=require('unplugin-auto-import/webpack')(...autoImportConfig)报错 TypeError:Foundnon-callable@@iterator原因:使用...扩展符的时候该对象是不可迭代对象。这里  autoImportConfig是一个对象,该函数参数需要传入......
  • nonstatic data members 和 static data members
    在C++中,类的数据成员可以分为非静态数据成员(non-staticdatamembers)和静态数据成员(staticdatamembers)。非静态数据成员(non-staticdatamembers):非静态数据成员是类定义中没有使用static关键字声明的数据成员。对于这些数据成员,每个类的实例都有各自独立的内存空间,它们在对象......
  • grant create synonym to SCOTT
    ConnectedtoOracleDatabase11gEnterpriseEditionRelease11.2.0.1.0ConnectedasSYSTEM@ORCLSQL>grantcreatesynonymtoSCOTT;GrantsucceededSQL>connscott/tiger;ConnectedtoOracleDatabase11gEnterpriseEditionRelease11.2.0.1.0......
  • TS高级类型 Record、Pick、Partial、Required、Readonly、Exclude、Extract、Omit、No
    keyof获取类型内所有的key,即所有属性名,获取的是一个联合类型这里类型指:通过interface或type定义的类型;通过typeofxxx返回的类型等。keyof后面必须是类型,不能是具体的对象interfaceIPeople{name:string,age?:number,sex:string,}ty......
  • 删除docker images中为none的镜像
    查看现有镜像➜safelinedockerimagesREPOSITORYTAGIMAGEIDCREATEDSIZEchaitin/safeline-tengine1.5.125a6146e6aed13hoursago119MBchaitin/safeline-tenginelatest25a6146e6aed13hoursago119M......