自动搬运

查看原文

来自洛谷，原作者为

	MZ_CXQ **

搬运于2025-08-24 21:36:36，当前版本为作者最后更新于2019-08-21 11:31:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎踩踩我的博客

${\color{cyan}{>>Question}}$

二维偏序$dp$

方程很简单

令$f[i]$表示到$i$的方案数

有

写成前缀和的形式便是

暴力是$O(n^2)$(话说居然有70pts),考虑优化

观察可知$i$由$j$转移来有两个条件

$1.$ $j < i$

$2.$ $sum[j] <= sum[i]$

那可把$i$看成$(i,sum[i])$的点,就成了一个二维偏序问题

不了解二维偏序的可以康康这篇博客(其实逆序对就是最经典的二维偏序(动态逆序对就是三维偏序) )

可以离散化,也可以不离散化

离散化就离散$sum[i]$,$i$天然有序

不离散化就以$sum[i]$为第一关键字,$i$为第二关键字排序

外面都套个树状数组即可

但我太菜了,第一次处理树状数组$0$基准的情况($f[0] = 1$),犯了很多错才调出来,具体看代码吧

离散化版

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

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) x = -x , putchar('-');
    if(x > 9) out(x/10);
    putchar(x%10 + 48);
}
//-------------------------------------------------------

const int N = 1e5+7,mod = 1e9+9;
int n;
ll b[N],ans;

struct node {
	int pos;ll sum;
}p[N];

struct map {
	int pos;ll sum;
	bool operator < (const map &x) const {
		return sum == x.sum ? pos < x.pos : sum < x.sum;//sum < x.sum;
	}
}a[N];

void A(int pos,ll k) {
	for(int i = pos;i <= n;i += i&-i) b[i] = (b[i]+k)%mod;
}

ll Q(int pos) {
	ll res = 0;
	for(int i = pos;i;i -= i&-i) res = (res + b[i])%mod;
	return res;
}

int main() {
	//freopen("0.in","r",stdin);
	//freopen("my.out","w",stdout);
	int i; ll x;
	in(n);
	a[0].pos = a[0].sum = 0;
	for(i = 1;i <= n; ++i) p[i].pos = i,in(x),p[i].sum = p[i-1].sum + x,a[i].pos = i,a[i].sum = p[i].sum;
	sort(a,a+n+1);//debug a[0]
	p[a[0].pos].sum = 1; int _id = 1;
	for(i = 1;i <= n; ++i) {
		if(a[i].sum != a[i-1].sum) ++_id;//debug i-1越界 
		p[a[i].pos].sum = _id;
	}
	//for(i = 1;i <= n; ++i) cout << p[i].sum << endl;
	A(p[0].sum,1);
	for(i = 1;i <= n; ++i) {
		ans = Q(p[i].sum);
		A(p[i].sum,ans);
		if(i == n) out(ans);
		//out(ans),putchar('\n');
	}
	//out(ans);
	return 0;
}

不离散化版

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

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) x = -x , putchar('-');
    if(x > 9) out(x/10);
    putchar(x%10 + 48);
}
//-------------------------------------------------------

const int N = 1e5+7,mod = 1e9+9;
int n;
ll b[N],ans;
ll f[N];

struct node {
	int pos;ll sum;
	bool operator < (const node &x) const {
		return sum == x.sum ? pos < x.pos : sum < x.sum;
	}
}p[N];

void A(int pos,ll k) {
	for(int i = pos;i <= n+1;i += i&-i) b[i] = (b[i]+k)%mod;//debug n+1 -> n
}

ll Q(int pos) {
	ll res = 0;
	for(int i = pos;i;i -= i&-i) res = (res + b[i])%mod;
	return res;
}

int main() {
	//freopen("0.in","r",stdin);
	int i; ll x;
	in(n);
	p[0].pos = 1,p[0].sum = 0;
	for(i = 1;i <= n; ++i) p[i].pos = i+1,in(x),p[i].sum = p[i-1].sum + x;
	sort(p,p+n+1);
	for(i = 0;i <= n; ++i) {
		if(p[i].pos == 1) A(p[i].pos,1);
		f[p[i].pos-1] = Q(p[i].pos);
		ll x = f[p[i].pos-1];
		//if(p[i].pos == 1) A(p[i].pos,1);//debug//debug 
		if(p[i].pos == 1) continue;
		A(p[i].pos,x);
	}
	out(f[n]);
	//for(i = 1;i <= n; ++i) cout << f[i] << endl;
	return 0;
}

谢谢各位看官老爷支持,如果觉得还看得下去的话,不妨点个赞, 投个币（づ￣3￣）づ╭❤～

另外有意愿的大佬们可以去切一下这道题,一样的思路