区间（interval）

题目描述

　　zht有一个长度为n的排列P，现在zht想知道，有多少个由连续整数组成的区间[l,r][l,r]可以由PP中的两个区间[a,b],[c,d]拼出，其中1≤a≤b<c≤d≤n

　　例如P=[1,5,2,4,6,3，那么数字区间[5,6][5,6]可以由PP的区间[2,2][2,2]与[5,5][5,5]拼出。换句话说PP中这两个区间数字的并集为[l,r]

输入

第一行一个整数nn表示排列中数字个数。

第二行nn个数表示排列。

输出

一行一个正整数表示答案。

样例输入

5

1 4 5 3 2

样例输出

提示

数据范围：

10%的数据：n≤20n≤20

40%的数据：n≤2000n≤2000

另有10%的数据：Pi=iPi=i

100%的数据： 1≤n≤3∗105

solution

考虑dp 令f[l][r]表示权值取l，r时会形成多少联通块。

我们枚举r，假设已经知道了f[1~r-1][r-1] 问题是如何快速求出f[1~r][r]

我们假设r在排列中的位置为x 找出p[x-1]和p[x+1]

然后分类讨论L的位置，决定转移是否要加1或减一

可以线段树优化。

现在还有个问题：怎么求f值为1和2的个数

我们可以存最小值，次小值和出现次数。

因为不会减到0，所以不用推来推去

好高级的线段树

注意不能写bj>0 要写bj！=0！！！！！

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 300005

#define ls k<<1

#define rs k<<1|1

#define inf 1e9

#define ll long long

using namespace std;

int n,a[maxn],p[maxn];

ll ans=0;

struct node{

	int l,r;

	ll ma,va,mb,vb,bj;

	void out(){

		cout<<"l: "<<l<<' '<<"r "<<r<<' '<<"a "<<ma<<' '<<va<<' '<<"b "<<mb<<' '<<vb<<' '<<endl;

	}

}tree[maxn*4];

struct no{

	ll m,v;

}s[4];

bool C(const no &a,const no &b){

	return a.m<b.m;

}

void wh(int k){

	s[0].m=tree[ls].ma,s[0].v=tree[ls].va;

	s[1].m=tree[ls].mb,s[1].v=tree[ls].vb;

	s[2].m=tree[rs].ma,s[2].v=tree[rs].va;

	s[3].m=tree[rs].mb,s[3].v=tree[rs].vb;

	sort(s,s+4,C);

	ll n1=s[0].m,v1=s[0].v,n2=0,v2=0;

	for(int i=1;i<4;i++){

		if(s[i].m==n1)v1+=s[i].v;

		else {

			if(!n2)n2=s[i].m,v2=s[i].v;

			else if(n2==s[i].m)v2+=s[i].v;

		}

	}

	tree[k].ma=n1,tree[k].va=v1;

	if(n1==inf)tree[k].mb=n1,tree[k].vb=0;

	else tree[k].mb=n2,tree[k].vb=v2;

}

void build(int k,int L,int R){

	tree[k].l=L,tree[k].r=R;

	if(L==R){

		tree[k].ma=tree[k].mb=inf;

		return;

	}

	int mid=tree[k].l+tree[k].r>>1;

	build(k*2,L,mid);build(k*2+1,mid+1,R);

	wh(k);

}

void up(int k,int v){

	tree[k].ma+=v;tree[k].mb+=v;tree[k].bj+=v;

}

void down(int k){

	if(tree[k].bj!=0){

		up(k*2,tree[k].bj);up(k*2+1,tree[k].bj);

		tree[k].bj=0;

	}

}

void add(int k,int li,int ri,int v){

	if(li>ri)return;

	if(tree[k].l>=li&&tree[k].r<=ri){

		up(k,v);return;

	}

	down(k);

	int mid=tree[k].l+tree[k].r>>1;

	if(li<=mid)add(k*2,li,ri,v);

	if(ri>mid)add(k*2+1,li,ri,v);

	wh(k);

}

void ch(int k,int pl)

{

	if(tree[k].l==tree[k].r){

		tree[k].ma=1;tree[k].va=1;return;

	}

	down(k);

	int mid=tree[k].l+tree[k].r>>1;

	if(pl<=mid)ch(k*2,pl);

	else ch(k*2+1,pl);

	wh(k);

}

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);p[a[i]]=i;

	}

	build(1,1,n);

	for(int i=1;i<=n;i++){

		int x=p[i];

		int l=a[x-1],r=a[x+1];

		if(l>r)swap(l,r);

		if(l>=i)

			add(1,1,i-1,1);

		if(r>=i&&l<i)

			add(1,l+1,i-1,1);

		if(r<i){

			add(1,1,l,-1);add(1,r+1,i-1,1);

		}

		if(tree[1].ma<3)ans+=tree[1].va;

		if(tree[1].mb<3)ans+=tree[1].vb;

		ch(1,i);

	}

	cout<<ans<<endl;

	return 0;

}

/*

5

1 4 2 5 3

*/

巴特西

区间（interval）

区间（interval）

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章