线段游戏-BZOJ4881-解题报告

i207M

·

2018-06-14 17:09:08

·

个人记录

题目总结

给定一个排列，要求出把它分成两个单增序列的方案数；

数据范围

1<=n<=100000

解题思路

此题可以线段树DP做，然而有更好的方法；

我们先求出有没有解：先求出最长下降子序列，假如长度大于2，一定无解（为什么？根据抽屉原理，一定任何一个序列包含两个下降数）

然后，我们建立一个set，将这些数一个一个加到set里，在加入之前，先将set中比当前数大的数全都删掉，然后将这些数（包含插入的数）中最大的数加到set中去，最后若set中还剩m个数，答案就是2^m；

因为一定有解，所以对于同一个i和a[i]，任意两个满足ja[i]的j和j'，j和j'当前一定属于两个不同的联通块，而现在他们都要和i连边，那么把i加进来之后他们就都变成一个联通块了，答案就是2^联通块个数；

很容易想到，对于一个靠后的较小的数，他一定和比他大的数不能同时被选，这样就可以把他们压成一个联通块，用最大的数代表他们（一个联通块内分成两个集合）

易错误区

代码展示

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define ll long long

#define inf 0x3f3f3f3f

#define ri register int

#define il inline

#define fi first

#define se second

#define mp make_pair

#define pi pair

#define mem0(x) memset((x),0,sizeof (x))

#define mem1(x) memset((x),0x3f,sizeof (x))

il char gc() {

static const int BS = 1 << 22;

static unsigned char buf[BS], *st, *ed;

if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);

return st == ed ? EOF : *st++;

}

#define gc getchar

templatevoid in(T &x)

{

x = 0; bool f = 0; char c = gc();

while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}

while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}

if (f) x = -x;

}

#undef gc

void out(int x) {

if (x < 0) putchar('-'), x = -x;

if (x > 9) out(x / 10);

putchar(x % 10 + '0');

}

#define N 100010

#define md 998244353

#define int ll

int p[N], d[N];

int g[N], f[N];

int n, ans = 1;

set >s;

void print() {

puts("****************");

for (set::iterator it = s.begin(); it != s.end(); ++it) {

printf("A %d\n", *it);

}

}

signed main() {

in(n);

for (ri i = 1; i <= n; ++i) in(p[i]), d[i] = -p[i];

mem1(g);

for (ri i = 1, t; i <= n; ++i) {

t = upper_bound(g + 1, g + 1 + n, d[i]) - g;

f[i] = max(f[i - 1], t); // cout << f[i] << endl;

g[t] = min(g[t], d[i]);

}

if (f[n] >= 3) {

puts("0");

return 0;

}

for (ri i = 1, t; i <= n; ++i) {

t = p[i];

while (!s.empty() && *s.begin() > p[i]) {

t = max(t, *s.begin());// printf("C %d\n", *s.begin());

s.erase(s.begin());// printf("C %d\n", *s.begin());

}

s.insert(t);

//print();

}

ri t = s.size();

while (t--) (ans *= 2) %= md;

printf("%lld", ans);

return 0;

}

/*

int f[N];

int find(int x){

return x==f[x]?x:f[x]=find(f[x]);

}

bool cmpy(int x,int y){

int fx=find(x),fy=find(y);

if(fx==fy) return 0;

if(fy>fx) f[fy]=fx;

else f[fx]=fy;

return 1;

}

*/

/*

int v[M], u[M], w[M], nx[M];

int cnt, head[N];

il void add(int uu, int vv, int ww) {

u[++cnt] = uu, v[cnt] = vv, w[cnt] = ww, nx[cnt] = head[uu];

head[uu] = cnt;

}

*/

/*

struct Edge {

int u,v,w,nx;

Edge() {}

Edge(int uu,int vv,int ww,int nxt) {

u=uu,v=vv,w=ww,nx=nxt;

}

friend bool operator<(const Edge& a,const Edge& b) {

return a.w

}

} edge[M];

int cnt,head[M];

il void add(int u,int v,int w) {

edge[++cnt]=Edge(u,v,w,head[u]);

head[u]=cnt;

}

*/