2022-9-11总结

Zero-Sum Ranges 2

我们将数列的前缀和画到坐标系上，这玩意长得大概像个树(?)，

我们自顶向下构造这个树，每次添加一层。

设 $f_{len, cnt, holw}$ 为目前构造了长度为 $len$ 的序列， 有 $cnt$ 个和为 $0$ 的区间， 中间有 $hole$ 个"洞"。

转移就可以 f[len+x][cnt+C(x,2)][x-(hole+2)] += f[len][cnt][hole] 了。

填好表格之后答案为 $f_{2n+1,k,0} + \sum{f_{i,j,k}*f_{2n+1-i,k-j,k-1}}$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 65;

int n, m, l;
ll fact[N];
ll f[N][N][N*N];

void prework();
ll C(ll n, ll m);

int main()
{
	prework();
	cin >> n >> m;
	l = n*2+1;
	f[0][0][0] = 1;
	for(int i = 0; i < l; i++)
	for(int j = 0; j <= n; j++)
	for(int k = 0; k <= m; k++)
		if(f[i][j][k] != 0)
			for(int s = j+1; i+s <= l; s++)
				f[i+s][s-j][k+s*(s-1)/2] += C(s-1,j)*f[i][j][k];
	ll ans = f[l][1][m];
	for(int i = 1; i <= l; i++)
	for(int j = 2; j <= l; j++)
	for(int k = 0; k <= m; k++)
		ans += f[i][j][k]*f[l-i][j-1][m-k];

	cout << ans << endl;
}

ll C(ll n, ll m)
{
	if(n < m) return 0;
	return fact[n]/fact[m]/fact[n-m];
}
void prework()
{
	fact[0] = 1;
	for(int i = 1; i < N; i++)
		fact[i] = fact[i-1]*i;
}

Gateau

Stop learning useless algorithms, go and solve problems, learn how to use binary search.

我们将 $A$ 的前缀和记为 $s_i$。

对于第 $i(i \le n)$ 个人，他的要求可以表示为: $b_i \le s_{i+n-1} - s_{i-1}$。

对于第 $i(i > n)$ 个人， 他的要求可以表示为 $s_{2n} - b_i \ge s_{i-1}-s_{i-n}$。

综合起来，令 $l_i = b_i, r_i = s_{2n} - b_{i+n}$，则 $A$ 应该满足:

$l_i \le s_{i+n-1} - s_{i-1} \le r_i (1 \le i \le n)$

如果给定 $s_n$，我们就可以求出 $s_{n-1}$ 和 $s_{2n-1}$。

同时，当 $s_n$ 越大， $s_{2n-1}$ 和 $s_n$ 就越大，最后我们需要判定是否存在一个 $s_n$ 使得 $s_{n-1} \le s_n$ 且 $s_{2n-1} \le s_{2n}$。

我们可以二分 $s_n$，这样就得到了 $O(n \log A)$ 的做法。

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 3e5+10;

int n;
int b[N], sum[N];

bool check(int x);
void get(int x);

int main()
{
	cin >> n;
	for(int i = 0; i < n*2; i++)
		cin >> b[i];

	int l = 0, r = 2e9, mid;
	while(l < r)
	{
		mid = (l+r)>>1;
		if(check(mid))
			r = mid;
		else
			l = mid+1;
	}
	cout << l << endl;
}

bool check(int x)
{
	for(int i = 0; i < n; i++)
		if(b[i]+b[i+n] > x) return false;
	sum[n] = b[0]; get(x);
	int p = sum[n-1];
	sum[n] = max(sum[n], p);
	if(sum[n] > x-b[n]) return false;
	get(x);
	if(p != sum[n-1]) return false;

	return x >= sum[n*2-1];

}
void get(int x)
{
	for(int i = 1; i < n; i++)
	{
		sum[i] = max(sum[i-1], sum[i+n-1]+b[i+n]-x);
		sum[i+n] = max(sum[i+n-1], sum[i-1]+b[i]);
	}
}

平面点对

二维问题考虑分别维护两维。

题目要求先选 $x$ 最小的，再选 $y$ 最小的。

所以我们可以对着 $x$ 轴建一棵线段树， 每个节点存对应的 $x=i$ 这条直线上de的 $y$ 坐标的值。

查询的时候进行一个线段树二分，就可以快速找到满足条件的最小的 $x$ 值。

然后在线段树的每个叶子节点开一个 multiset，就可以查询 $y$ 值了。

注意坐标范围较大需要先离散化一下。

时间复杂度 $O(n \log n)$

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
const int N = 2e5+10;
const int INF = 0x3f3f3f3f;

namespace tr {
    struct node {
        int ls, rs;
        multiset<int> s;
    }a[N*2];
    int lim, root, node_cnt;
    void build(int &i = root, int l = 1, int r = lim);
    void erase(int x, int y, int i = root, int l = 1, int r = lim);
    void insert(int x, int y, int i = root, int l = 1, int r = lim);
    pair<int,int> find(int x, int y, int i = root, int l = 1, int r = lim);
}

char opt[N][8];
int x[N], y[N];
int lsh[N], lcnt;

int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> opt[i] >> x[i] >> y[i];
        lsh[i] = x[i];
    }
    sort(lsh+1, lsh+n+1);
    lcnt = unique(lsh+1, lsh+n+1)-lsh-1;
    for(int i = 1; i <= n; i++)
        x[i] = lower_bound(lsh+1, lsh+lcnt+1, x[i])-lsh;
    tr::lim = lcnt; tr::build();
 
    for(int i = 1; i <= n; i++)
    {
        if(opt[i][0] == 'a')
            tr::insert(x[i], y[i]);
        else if(opt[i][0] == 'r')
            tr::erase(x[i], y[i]);
        else
        {
            x[i] += 1, y[i] += 1;
            if(x[i] > lcnt) { cout << "-1\n"; continue; }
 
            auto ans = tr::find(x[i], y[i]);
            ans.first = lsh[ans.first];
            if(ans.second != INF)
                cout << ans.first << " " << ans.second << "\n";
            else
                cout << "-1\n";
        }
    }
}
 
namespace tr {
    #define ls(i) a[i].ls
    #define rs(i) a[i].rs
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void build(int &i, int l, int r)
    {
        i = ++node_cnt;
        if(l == r) return void();
        build(ls(i), l, lmid);
        build(rs(i), rmid, r);
    }
    void insert(int x, int y, int i, int l, int r)
    {
        a[i].s.insert(y);
        if(l == r) return void();
        if(x <= lmid) insert(x, y, ls(i), l, lmid);
        if(x >= rmid) insert(x, y, rs(i), rmid, r);
    }
    void erase(int x, int y, int i, int l, int r)
    {
        auto it = a[i].s.lower_bound(y);
        a[i].s.erase(it);
        if(l == r) return void();
        if(x <= lmid) erase(x, y, ls(i), l, lmid);
        if(x >= rmid) erase(x, y, rs(i), rmid, r);
    }
    pair<int,int> find(int x, int y, int i, int l, int r)
    {
        if(l == r)
        {
            auto it = a[i].s.lower_bound(y);
            if(it != a[i].s.end())
                return {l, *it};
            else
                return {l, INF};
        }
        auto &ls_s = a[ls(i)].s, &rs_s = a[rs(i)].s;
        if(x <= lmid and ls_s.lower_bound(y) != ls_s.end())
        {
            auto tmp = find(x, y, ls(i), l, lmid);
            if(tmp.second != INF) return tmp;
             
        }
        if(rs_s.lower_bound(y) != rs_s.end())
            return find(x, y, rs(i), rmid, r);
        else
            return {114514, INF};
    }
}