分类： 题解

这一题据说被放在了线段树这个模块下面。
我想了很久很久。想到了一种做法。但是一写就感觉很麻。
想着想着，算了一下复杂度，然后大喊一声，MADE！
仔细一想，询问2E5，值域1E5。大力上分块啊，\(O(Nsqrt(M))\approx 6E7\)不满。搞什么线段树啊，真是的。
好的，那么大力上分块。
具体应该要怎么分块呢？
对于每一块，我们定义一种标记。
如果标记是0，说明这个块是空的，那么就可以直接修改；
如果标记是一个正整数，说明这个块被该正整数完全包含，也可以直接修改，并将该标记指的数放入删除集合；
如果标记是-1，说明这个块里面包含多个询问。此时同样暴力修改。
为什么这样做的复杂度是对的呢？首先，如果一个块，如果它包含多个询问，那么要么它包含的是整个询问，要么它包含的是询问的一段。
因此，对于一个询问，它最多只可能被暴力修改两次。
所以这种做法是可行的。

不过分块写起来还是挺麻的。调了半天没调出来，然后看到了一个神仙做法，就抄过来了：
具体来说，就是把Set当作红黑树用。
太猛了。

#include<cmath>
#include
#include
#include<cstring>
#include<set> 
using namespace std;
#define MAXN 100000
int n;
struct data{
	int l,r;
	bool operator <(const data &A)const{
		return (this->l==A.l)?(this->l<A.r):(this->l<A.l);
	}
};

set<data> st;
void init(){
	scanf("%d",&n);
	char ch[5];
	int l,r,ans;
	for(int i=1;i<=n;++i){
		cin>>ch;
		if(ch[0]=='B'){
			printf("%lld\n",st.size());
		}else{
			scanf("%d%d",&l,&r);
			data X=(data){l,r};
			ans=0;
			set<data>::iterator it=st.lower_bound(X);
			while(1){
				it=st.lower_bound(X);
				if(it->l<=X.r&&X.l<=it->r){
					++ans;
					st.erase(it);
					continue;
				}
				it=st.lower_bound(X);
				if(it!=st.begin()){
					--it;
					if(it->l<=X.r&&X.l<=it->r){
						++ans;
						st.erase(it);
						continue;
					}
				}
				break;
			}
			st.insert(X);
			printf("%d\n",ans);
		}
	}
}
int main(){
	init();
	return 0;
}

//大力分块的假做法，直到现在都不懂bug在哪里。第k块表示k*blck~(k+1)*blck-1的值。 
int n,cnt=0,blck,L[200005],R[200005],rst,TOP;
int V[317],v[100005];
char ch[4];
bool bo[200005];
inline void prpr(){
    blck=sqrt(MAXN);
    rst=MAXN%blck;
    TOP=MAXN-rst;
    memset(V,0,sizeof(V));
    memset(v,0,sizeof(v));
    memset(bo,0,sizeof(bo));
}
int rt=0;
inline void delB(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(V[i]==x){
            V[i]=0;
        }
    }
}
inline void delb(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(v[i]==x){
            v[i]=0;
        }
    }
}
inline void del(const int &x){
    bo[x]=0;
    ++rt;--cnt;
    int l=L[x],r=R[x];
    if(r/blck-1<(l/blck+1)){
        delb(l,r,x);
        return;
    }
    delB(l/blck+1,r/blck-1,x);
    delb(l,(l/blck+1)*blck-1,x),delb((r/blck)*blck,r,x);
    
}
inline void addb(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
    	if(V[i/blck]!=x){
    		V[i/blck]=-1;
		} 
        if(!bo[v[i]]){
            v[i]=x;
        }else{
            del(v[i]);
            v[i]=x;
        }
    }
}
inline void clr(const int &x){
    for(int i=x*blck;i<(x+1)*blck;++i){
        if(bo[v[i]]){
            del(v[i]);
        }
    }
}
inline void addB(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(!V[i]){
            V[i]=x;
        }else if(V[i]>0){
            if(bo[V[i]]){
                del(V[i]);
            }
            V[i]=x;
        }else{
            clr(i);
            V[i]=x;
        }
    }
}
inline int add(const int &l,const int &r,const int &x){
    rt=0;
    if(r/blck-1<(l/blck+1)){
        addb(l,r,x);
        return rt;
    }
    addB(l/blck+1,r/blck-1,x);
    addb(l,(l/blck+1)*blck-1,x),addb((r/blck)*blck,r,x);
    return rt;
}
void init(){
    prpr();
    scanf("%d",&n);
    int l,r;
    for(int i=1;i<=n;++i){
        cin>>ch;
        if(ch[0]=='B'){
            printf("%d\n",cnt);
        }else{
            bo[i]=1;++cnt;
            scanf("%d%d",&l,&r);
            printf("%d\n",add(l-1,r-1,i));
            L[i]=l-1,R[i]=r-1;
        }
    }
}
int main(){
    init();
    return 0;
}

 

这一题的题面很复杂，但形式化地概括则很简单：

对于一个长度为n的全排列，求出其中有多少排列A满足，对于任意i属于n，$$(A_{i}-A{i-1})*(A_{i}-A_{i+1})>=0;$$

然后我们观察排列的特点，我们可以发现，对于排列A中的一个元素\(A_{i}\)，我们可以发现，如果\(A_{i}\)是山峰，那么将\(A_{i}\)的值无论添加多少，都不改变这个序列的可居住性；对于山谷，则反之。
于是，我们可以发现，一个合法的排列，如果我们要在它末尾添上一个数让它形成一个新的合法排列，对于除了最后一个数以及这个数是属于山峰以及山谷以外，我们不关心其他的属性。
因此我们可以用\(f[i][j][k]\)表达当前长度为i，最后一个数为j，最后一个数的状态为k的时候的状态数。其中k==0表示山谷，而k==1表示山峰。
则很容易可以得到状态转移方程：
$$f[i][j][k]+=f[i-1][l][k\ xor\ 1](k?(0<l<=j-1):(j-1<l<=i))$$
但是这样子的复杂度是N^3的，对于4200的数据显然是不能通过的。这时候考虑优化。
我们发现求和的东西是一段区间，因此我们可以考虑前缀优化。
这样子就将复杂度从\(n^3\)降低到了\(n^2\)，于是可以通过。
但是这样子需要的空间是3E7的，对于128MB的空间是非常危险的，这时候考虑滚动数组优化，这样是可以通过的。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,p,f[4205][2],pre[4205][2];
void init(){
    scanf("%lld%lld",&n,&p);
    int l,r;
    f[1][1]=f[1][0]=pre[1][0]=pre[1][1]=1;
    for(int i=2;i<=n;++i){
        pre[i][0]=pre[i-1][0],pre[i][1]=pre[i-1][1];
        for(int j=1;j<=i;++j){
            for(int k=0;k<=1;++k){
                l=k?0:j-1;
                r=k?j-1:i;
                f[j][k]=(pre[r][k^1]-pre[l][k^1]+p)%p;
//                printf("(%d,%d)[%d,%d]%lld|",l,r,pre[l][k^1],pre[r][k^1],f[j][k]);
            }
//            printf(" ");
        }
        pre[0][0]=pre[0][1]=0;
        for(int j=1;j<=i;++j){
            pre[j][0]=(pre[j-1][0]+f[j][0])%p;
            pre[j][1]=(pre[j-1][1]+f[j][1])%p;
        }
//        puts("");
    }
    long long ans=(pre[n][0]+pre[n][1])%p;
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
}

 

Q：为什么这个方程不会重复统计呢？
如果只关心上一个元素的大小，排列中的元素可能重复出现了。

A：不会重复统计，感性证明如下：

首先我们假定对于上一个A，使得：

$$ |A|==i-1 $$

并没有重复统计。
那么我们插入一个新的元素\(i\)时，产生的新序列必然是 本质不同 的。
我们对于\(A_{i-1}\)是山峰和山谷分别讨论。
如果\(A_{i-1}\)是山峰，那么新插入的元素，必然比\(A_{i-1}\)小，并且一定是由将序列中大等于【某个小于等于\(A_{i-1}\)的一个数\(l\)】的所有数提升一，然后将新插入的元素定义为\(l\)。
这时候，\(i-1\)位上的数是\(A_{i-1}+1\)，而\(i\)位上的数则是\(l\)。
在这种情况下，最后两位是\(A_{i-1}+1\)与\(l\)。显然对于每一个本来已有的\(A_{i-1}\)，它们在新的序列中都会加且仅加1。
这样，所有新增的组合的最后两位都是 本质不同 的，因此序列本质不同。
对于山谷，情况类同于山峰，同样可以证明不会产生重复的后两位，进而不会产生本质相同的数列。

而对于 $$|A|==1$$ ，结果显然是1，没有重复统计。
从而归纳得出全部都没有重复统计。

看起来是一道很简单的题，但是细节巨多，消耗了我大量的提交次数。如果是比赛我怕不是凉了。

很显然是一道DP题。
很容易可以想到的是暴力枚举，然而这样做的复杂度是O(n^2*n^2k)的，很很很很显然可以发现是不可行的。
观察数据范围，我们可以注意到， m<=2，因此很容易可以想到状压DP。
具体来说，当m==2时，用f[i][j][l]表示，当前处于第i行，第i行的状态为j，已经使用了l个子矩阵时，最大的和。
则状态转移方程是：

f[i][0][l]=Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l]));
f[i][1][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l]))+b[i];
f[i][2][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l]))+a[i];
f[i][3][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l]))+a[i]+b[i];

并且我们很容易可以得到边界条件，即：

f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][1]=a[1]+b[1];

另外需要考虑m==1的情况，事实上这种情况更容易考虑：状态转移方程是：

f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 

初始化f[1][0][0]=0,f[1][1][1]=a[1];

然而交上去全wa
回头考虑这个问题我们可以发现一个很尴尬的事情：当上一行两个取的时候，我们并不知道它到底是「两列分别取」还是「两列一起取」。
因此，对于11的状态，我们应当拆成两个部分：
f[i][3][l]表示上一行的两列是分别取的。于是得到状态转移方程。
f[i][4][l]表示上一行的两列是合在一起取的。

f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];

然而这样子还是全WA。
仔细观察一下我们的状态转移方程，我们发现存在一些l-2的状态，那么我们应该分两类讨论：l==1或l>=2.
这样大概就能通过了。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
int n,m,k,f[105][5][15],a[105],b[105];

void slv1(){
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    f[1][0][0]=0,f[1][1][1]=a[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=0;
        for(int l=1;l<=k;++l){
            f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
            f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 
        }
    }
    int ans=-0x3f3f3f3f;
    printf("%d",Max(f[n][0][k],f[n][1][k]));
    return;
}
void slv2(){
    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i],&b[i]);
    }
    f[0][0][0]=0;
    f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][2]=a[1]+b[1],f[1][4][1]=a[1]+b[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=f[i][2][0]=f[i][3][0]=f[i][4][0]=0;
        for(int l=1;l<=k;++l){
                f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
                f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
                f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
                f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];
                if(l<2){
                    continue;
                }
                f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
        }
    }
    /*
    for(int i=1;i<=n;++i){
        for(int l=0;l<=k;++l){
            for(int j=0;j<5;++j){
                printf("%d ",f[i][j][l]);
            }
            puts("");
        }
        puts("");
    }*/
    int ans=-0x3f3f3f3f;
    for(int i=0;i<5;++i){
        ans=Max(ans,f[n][i][k]);
    }
    printf("%d",ans);
}
void init(){
	scanf("%d%d%d",&n,&m,&k);
	memset(f,-1,sizeof(f));
	if(m==1){
	    slv1();
    }
    if(m==2){
        slv2();
    }
}
int main(){
	init();
	return 0;
}