CF558E A Simple Task

开一颗珂朵莉树,对于每个新的查询,先把l-1,l之间和r,r+1之间split开,然后对于剩下的部份用桶排序并暴力合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
const int N=100005;

struct Data{
	int l;int r;char id;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
	int l=it->l,r=it->r;char id=it->id;
	if(X<l||X>=r){
		return;
	}
	st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
	for(int i=0;i<26;++i){
		bckt[i]=0;
	}
}
inline void uni(int l,int r,int op){
	std::set<Data>::iterator itx,ity;
	itx=st.lower_bound((Data){0,l-1,0});
	split(itx,l-1);
	ity=st.lower_bound((Data){0,r,0});
	split(ity,r);
	itx=st.lower_bound((Data){0,l,0});
	ity=st.lower_bound((Data){0,r,0});
	++ity;
	for(std::set<Data>::iterator it=itx;it!=ity;++it){
		bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
	}
	st.erase(itx,ity);
	int loc,nl=l;
	for(int i=0;i<26;++i){
		loc=op?i:(26-i-1);
		if(bckt[loc]<=0){
			continue;
		}
		st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
		nl+=bckt[loc];
	}
	clr();
}
inline void prnt(){
	for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
		for(int j=it->l;j<=it->r;++j){
			putchar(it->id);
		}
	}
	puts("");
}
inline void init(){
	scanf("%d%d",&n,&q);
	std::cin>>ch+1;
	for(int i=1;i<=n;++i){
		st.insert((Data){i,i,ch[i]});
	}
	int l,r,op;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&l,&r,&op);
		uni(l,r,op);
//		prnt();
	}
	prnt();
}

int main(){
	init();
	return 0;
}

CF527C Glass Carving

开四个set,分别存切割的刀以及每个区间段,然后每次各自从行和列取最长的区间段,乘一起即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;


ll w,h;
std::set<ll> st[2];
std::multiset<ll> sm[2];
std::multiset<ll>::iterator it;

inline void init(){
	char ch[5];ll x,l,r;int id;
	std::cin>>ch+1;scanf("%lld",&x);
	id=(ch[1]=='H');
	set<ll> &nst=st[id];
	multiset<ll> &nsm=sm[id];
	nst.insert(x);
	it=nst.find(x);
	--it;l=*it;
	++it,++it;r=*it;
	it=nsm.find(r-l);
	nsm.erase(it);nsm.insert(r-x);nsm.insert(x-l);
	it=sm[0].end();--it;l=*it;
	it=sm[1].end();--it;r=*it;
	printf("%lld\n",l*r);
}

int main(){
	scanf("%lld%lld",&w,&h);
	int T;
	scanf("%d",&T);
	st[0].insert(0),st[0].insert(w);
	st[1].insert(0),st[1].insert(h);
	sm[0].insert(w),sm[1].insert(h);
	while(T--){
		init();
	}
	return 0;
}

lp3902 递增

最长上升子序列裸题。
dp+二分即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

int main(){
	init();
	return 0;
}

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询,那就可以考虑差分。
我们考虑将数列差分,维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D},就变成了三个操作:
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

int main(){
	init();
	return 0;
}

lp2757 [国家集训队]等差子序列

因为只要求存在性,故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ,于是用两个 bitset 分别维护前缀桶和后缀桶,稍微左右移一下求交即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
/*

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp5431 【模板】乘法逆元2


挺套路的。
先计算出所有数的积的逆元,再计算除了这个数以外的数的积,然后乘一起,这样就完成了线性求逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=5000005;
inline int rd(){
	int rt=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
	return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
	int RT=1;
	while(X){
		if(X&1){
			RT=1ll*RT*A%MOD;
		}
		A=1ll*A*A%MOD;X>>=1;
	}
	return RT;
}

void init(){
	scanf("%d%d%d",&n,&MOD,&k);
	int pl=1;
	pr[0]=sf[n+1]=1;
	for(int i=1;i<=n;++i){
		a[i]=rd();
	}
	for(int i=1;i<=n;++i){
		pr[i]=1ll*pr[i-1]*a[i]%MOD;
	}
	pl=pw(pr[n],MOD-2);
	for(int i=n;i>=1;--i){
		sf[i]=1ll*sf[i+1]*a[i]%MOD;
	}
	int nk=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		nk=1ll*nk*k%MOD;
		ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
	}
	printf("%d\n",ans);
	
}
int main(){
	init();
	return 0;
}

lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。

题目的题意就是,求 n 个点的点、边均有标号的生成树个数。

n 个点的无根有标号生成树个数,根据某个叫做 Cayley 的古老定理, 值是:

当然,由于边有标号,所以这里的值还要乘上一个​。

问题是 Cayley 定理要如何证明。

一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造,我们发现,有且仅有 ​ 种不同的方法来构造一棵有标号无根树。

这个序列是如何构造的呢?

我们考虑递归地构造这个序列。对于当前的树,我们选其中的编号最小的叶子节点,将它的相邻点——显然是唯一的——加入序列,然后删掉这个叶子节点。

这样,我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。

由此我们可以构造出这个序列。

通过 Prufer 序列,我们无损地将一棵有标号无根树的信息压缩成了一个序列。

那么要怎么把 Prufer 序列还原为一棵有标号无根树呢?我们有一种系统的方法。

首先选择一个数,这个数既不在已有的树中,也不在当前的序列中,并且它最小。那么,我们就可以确定,这个数便是我们当前要处理的叶子节点。

然后,我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。

是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢?

假设我们当前正在处理第 i 个节点,序列中剩下 k 种数,那么已经被作为叶子节点,已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点,至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ,所以叶子节点必然不会不够。

那么完成最后一步以后叶子节点会不会有剩呢?每个节点会被连接的次数正好是它在序列中出现的次数 +1 ,这也就意味着,总度数恰好是 2n-2 ,由于每一条边都无向,所以构成的正好是一张 n-1 条边的图。

最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的,我们不妨尝试证明它无环。

我们称,一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」,那么每个点的向上连边操作会且仅会发生一次。在这种情况下,环会出现,只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。

然而,向上连边的目标,一定还在 Prufer 序列中,而可以向上连边的点,一定不在 Prufer 序列中。我们于是证明了这张图无环。

既然这张 n-1 条边的图无环,那么它一定连通。

由此,我们发现,每一棵树都能唯一对应地生成一个 Prufer 序列,并且每一个 Prufer 序列都能生成一棵树。

这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;

inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;
			RT%=MOD;
		}
		A*=A;A%=MOD;X>>=1;
	}
	return RT;
}
int n;
void init(){
	scanf("%d",&n);
	ll fac=1;
	for(int i=1;i<n;++i){
		fac=fac*i%MOD;
	}
	printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
	init();
	return 0;
}

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 \(S\) ,其中 \(S_i\) 表示,长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\), 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。 问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢? 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ,足以通过此题。 具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

lp4980 【模板】Polya定理

Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂,在这里仅介绍其内容。
Burnside引理的内容是这样的:在置换意义下本质不同的染色方案数,等于单个置换不会改变的染色方案数的平均值。
那么,单个置换不会改变的染色方案数要怎么求呢?我们不妨把置换关系建成一张图,那么这张图必然由若干个环构成。也就是说,对于同一种置换,可能存在若干个环,而每个初始状态就是环上的一个节点。Polya定理描述的就是,某一种置换不会改变的方案数,等于颜色数的「这个置换对应的循环节个数」

阐述了上述两个定理,现在我们来看这一题。
我们观察到,这个环上存在 n 种置换。对于置换 i 而言,它的循环大小是:
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着,它的循环个数是:
$$
\gcd(n,i)
$$
那么我们要求的答案就是:
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的,我们无法接受。
我们不妨考虑枚举这个公因子。那么,容易证明的是,每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)

这是因为, d 是 \(\frac{n}{d}\) 个数的因数,而这些数中,如果它和\(\frac{n}{d}\)存在公因子的话,那么它和n的最大公因数必然大于d。

所以,我们求的就是:
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。

然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上,由于我们要取的因数的值域是 \(10^9\) ,我们无法使用欧拉筛来预处理,而需要现场做。

这样的复杂度是不是对的呢?它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的,但由于我并不会分析的一些性质,它不会达到这个值。因此可以通过此题。

另:括号忘记加,爆O泪两行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;RT%=MOD;
		}
		A*=A;A%=MOD,X>>=1;
	}
	return RT;
}
int n;
inline int phi(int X){
	int RT=1;
	for(int i=2;i*i<=X;++i){
		if(X%i==0){
			X/=i;RT*=i-1;
			while(X%i==0){
				X/=i;RT*=i;
			}
		}
		if(X==1){
			break;
		} 
	}
	if(X>1){
		RT*=X-1;
	}
	return RT;
}
void init(){
	scanf("%d",&n);
	ll ans=0;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
			if(i*i!=n){
				ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
			}
			ans%=MOD;
//			printf("%d %lld\n",i,ans);
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

CF102268C

贪心构造即可。
具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以及x(贡献是下标比x小且<-x)的数。
贪心地构造,可以保证x只出现一次。暴力枚举检验即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
	scanf("%d%lld",&n,&m);
	for(int i=0;i<=n;++i){
		bckt[i]=0;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		a[p[i]]=-n+i-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&q[i]);
		if(m==0){
			b[q[i]]=n;
		}else if(m>=q[i]-1){
			m-=q[i]-1;
			b[q[i]]=-1;
		}else{
			for(int j=1;j<q[i];++j){
				++bckt[a[j]+n];
			}
			for(int j=1;j<=n;++j){
				bckt[j]+=bckt[j-1];
			}
			for(int j=1;j<q[i];++j){
				if(bckt[a[j]+n]==m){
					m=0;b[q[i]]=-a[j]-1;
					break;
				}
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	puts("");
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}
	puts("");
}
int main(){
	init();
	return 0;
}

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。
它本质上就是一种优化的暴力:对于树上的信息,我们先把树以某种方式剖分,然后对于关键链直接上传,非关键链暴力合并。
其中,长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中,我们考虑暴力维护每个点为根的子树中每一层的信息,并把非长儿子的信息合并到长儿子中。
为了保证线性,我们使用指针。
我们建一个指针数组f,其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp,那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n,所以空间是足够的。
那就昨晚了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}

初赛复习:前缀表达式和后缀表达式

前缀表达式和后缀表达式——有时也被成为波兰表达式和逆波兰表达式——是对仅包含二元关系运算符和括号的表达式的变形。

事实上,前缀表达式和后缀表达式没有本质区别,因此只要会了前缀表达式,就会了后缀表达式——记住,前缀表达式是把运算符提到最前面的表达式,而后缀表达式反之。

对于一个这样的式子:
a+b/c
我们按照运算符优先级依次操作:
a+/bc
+a/bc
这样就将所有符号提到了整个式子的最前面。
对于包含括号的表达式,例如:
2+3(4-(5+6))/7 操作流程依然是按照运算符优先级的。 2+3(4-+5 6)/7
2+3(-4+5 6)/7 2+3(-4+5 6)/7
2+/3-4+5 6 7 +2/3-4+5 6 7

而如果要求后缀表达式,那操作就反之——从优先级最低的操作符开始,把操作符提到最右边。
还是一样的例子:
2 3(4-(5+6))/7+ 2 3(4-(5+6))7/+
2 3(4-(5+6))7/+ 2 3(4(5+6)-)7/+
2 3 4 5 6+-*7/+

初赛复习:OSI七层网络协议

ISO网络协议标准包括七层。

最底层的被称为物理层。这一层主要包括:
光纤、同轴电缆、双绞线、网卡、中继器、集线器
等硬件。它传输的是比特(bit)

物理层之上被称为数据链路层。数据链路层的主要硬件是网桥和交换机,这一层把数据封装成一种被称为帧(frame)的结构。

网络层是第三层。IP地址是这一层的内容。路由器也在这一层。

传输层是网络层之上的第四层。这一层主要管的是数据包的运输。TCP协议UDP协议都是传输层协议。

会话层是第五层,没看到什么考点。

表示层主要负责数据转换,没看到什么考点。

应用层是最顶层,应用层协议包括Telnet(Windows的远程桌面)、FTPSNMP(这两个都是远程文件管理系统)、HTTPDNS(IP地址解析服务)等协议。它是直接展现给用户的一层。

初赛复习:主定理

对于形如:
$$T(n)=aT(\frac{n}{b})+f(n)$$
那么,我们可以用下述三个公式来刻画\(T(n)\)的渐近上下界。
$$f(n)=\Theta(n^{log_ba-\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(n^{log_ba})$$
$$f(n)=\Theta(n^{log_ba+\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(f(n))$$
$$f(n)=\Theta(n^{log_ba})\Rightarrow T(n)=\Theta(n^{log_ba}logn)$$
换而言之,就是,比较\(f(n)\)和\(\Theta(n^{log_ba})\)的级别。如果两者同级,就乘上一个log,否则就取较大的。

lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到一个n+1个数的序列,使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性,我们可以尝试把无序数对看成一条边,然后建一张图。在这种情况下,这个序列就是这张图上的一个遍历顺序,使得经过每一条边至少一次。
深入考虑,这个序列也只能经过每条边至多一次。这是因为,一条n条边的路径,恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中,恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点,我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上,只需从奇数入度点开始,就是合法的?
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是,为什么搜索的时候不会直接走到链的另一端,而是先把环跑完,或者反过来?
我们注意到把点加入答案数组的方式:对于两个栈——答案栈和搜索栈来说,点被加入的顺序是不仅相同的。
模拟一下,一个点能从搜索栈出来,被加入答案栈,当且仅当从这个点出发无路可走了。
显然,有且仅有终点是无路可走的。那么,无论终点是在什么时候被访问到的,只要它被访问到,那么它就会被立刻退出搜索栈并被加入答案栈,剩下的点也是同理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}

lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得:
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说,购买的A和B券的数量分别是:
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么,我们从j转移到i的方程是:
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设:
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$
那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。
通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意:要判一下分母不能等于极小数,否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得: $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说,购买的A和B券的数量分别是: $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么,我们从j转移到i的方程是: $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设: $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$ 那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。 通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意:要判一下分母不能等于极小数,否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp2564 SCOI2009 生日礼物

尺取法即可。
开一个桶维护珍珠的颜色,然后扫一遍。每一次将最前端的点弹出,然后移动至下一个合法点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
	scanf("%d%d",&n,&K);
	int T;
	for(int i=1;i<=K;++i){
		scanf("%d",&T);
		for(int j=1;j<=T;++j){
			++tp;
			scanf("%d",&a[tp].val);
			a[tp].id=i;
		}
	}
	std::sort(a+1,a+1+n,cmp);
	int ans=2147483647;
	int l=1,r=0;
	while(r<n){
		while(r<n){
			++r;
			if(!bckt[a[r].id]){
				++cnt;
			}
			++bckt[a[r].id];
			if(cnt==K){
				break;
			}
		}
		if(cnt==K){
			ans=min(ans,a[r].val-a[l].val);
		}
		while(l<=r){
			--bckt[a[l].id];
			if(!bckt[a[l].id]){
				--cnt;
				++l;
				break;
			}
			++l;
			if(cnt==K){
//				printf("%d %d %d\n",ans,l,r);
				ans=min(ans,a[r].val-a[l].val);
			}
			
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp2219 HAOI2007 修筑绿化带

我们知道,如果我们确定了每个大矩形包含的权值最小的小矩形,那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。

那么我们考虑用单调队列来预处理出每一个小矩形的权值,然后用二维线段树来维护这个权值,那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然,我们可以维护2n个单调队列来计算这个最大值。
那么,对于这题的强化板,我们该怎么做呢?
如果确定了右下角,那么整个矩形的权值是已经固定了的。那么,我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题,我们发现,每个花坛的最小值是可以预处理的。这样,我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂,且不要混淆单调队列里的数的意义。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1005;

int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
	scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&val[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
		}
	}
	for(int i=B;i<=n;++i){
		for(int j=A;j<=m;++j){
			b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
//			printf("%d ",b[i][j]);
		}
//		puts("");
	}
	for(int i=D;i<=n;++i){
		for(int j=C;j<=m;++j){
			a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
//			printf("%d ",a[i][j]);
		}
//		puts("");
	}
	int ans=0;
	for(int i=D+1;i<n;++i){
		for(int j=C+1;j<m;++j){
//			printf("%d %d\n",i,j);
			while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
			q[j].push_back(i);
			while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
		}
		while(!qq.empty()){qq.pop_back();}
		for(int j=C+1;j<m;++j){
			while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
			qq.push_back(j);
			while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
			if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

P1083 NOIP2012 借教室

本质上是区间减区间最小值。
考虑到先操作再询问,差分加前缀和即可。
对于题目要求的那个答案,我们找到第一个不合法的点,然后枚举每一个询问和它比较即可
复杂度O(n+m)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
typedef long long ll;
const int N=1000005;
ll a[N],val[N];
int qx[N],ql[N],qr[N];
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&qx[i],&ql[i],&qr[i]);
		val[ql[i]]+=qx[i],val[qr[i]+1]-=qx[i];
	}
	int loc=0;
	for(int i=1;i<=n;++i){
		val[i]+=val[i-1];
		if(val[i]>a[i]){
			loc=i;
			break;
		}
	}
	if(!loc){
		puts("0");
		return;
	}
	ll cnt=0;
	for(int i=1;i<=m;++i){
		if(ql[i]<=loc&&qr[i]>=loc){
			if(cnt+qx[i]>a[loc]){
				puts("-1");
				printf("%d\n",i);
				return;
			}else{
				cnt+=qx[i];
			}
		}
	}
}
int main(){
	init();
	return 0;
}