day4

正睿青岛

T1

给你一个序列a1,a2,…,an，我们称一个区间[l,r]为好的区间当且仅当al,al+1,…,ar这些数字最大值不超过最小值的k倍。
现在给你一个序列，问有多少个太阳区间。
注意：此题空间限制为16MB。

每个点为右端点的时候，左端点与他形成的区间中，最大值会影响一段一段的区间。就是当一个oooxooooi当前在i，最大值x，那么左边所有的端点与i形成的区间最大值都是x，所以可以用两个单调栈来记录最大值区间，和最小值区间。
最大值是递减的，最小值最递增的，所以越往右，越满足条件（什么叫越满足条件：最小值越大，最大值越小，k*最小值越大于最大值），一定有一个位置右边满足条件，左边不满足了，于是可以二分。
其实，将单调栈，改成单调队列（双端队列）就行了。 首先这些二分到的位置一定是在单调栈里的位置，所以如果队首不满足条件，弹出队首，知道满足。每次位置不断往右移。

T3

分数规划，二分答案，a[i] b[i] -=ans
60分线段树优化建图网络流，最大独立集
正解dp
dp[i]表示考虑到右侧第i个，每次枚举上次选的点j < i，然后左侧的覆盖区间在j~i的点就可以被选了（加入独立集），预处理前缀和则左侧覆盖的区间在(j,i)间的有多少个n^2。复杂度O(n^2logn)
优化：
每次枚举右侧的点时，总是在前面找一个最小的j，满足dp[j]+cost(i,j)最小，f[j] = dp[j] + cost(i, j)，所以就是max(f[i])。
更新f数组：每次计算完这个右端点后，将所有左侧区间为l~i的区间（就是以当前点为右端点的区间）的左侧点可以加入到1~l-1的f数组里。所以可以用线段树优化。
设f数组辅助，f[j]表示从i转移到当前点时，从j转移的代价。

for(i=1;i<=n;i++)
{
    dp[i]=max(f[1..n-1]); //线段树
    f[i]=dp[i]
    for  右端点为i的区间[l,r] w
      f[1...l-1]+=w //线段树
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef double LD;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 30005;
const LD eps = 1e-8;
const LD INF = 1e18;
struct Node{
    int w, l, r;
}A[N];
int B[N], n, m, k;
vector<int> vec[N];
LD ta[N], tb[N], mx[N << 2], tag[N << 2];
#define Root 0, m, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
inline void pushup(int rt) {
    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
inline void pushdown(int rt) {
    if (tag[rt] > -eps) {
        tag[rt << 1] += tag[rt], tag[rt << 1 | 1] += tag[rt];
        mx[rt << 1] += tag[rt], mx[rt << 1 | 1] += tag[rt];
        tag[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    mx[rt] = tag[rt] = 0;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(lson); build(rson);
}
void update(int l,int r,int rt,int L,int R,LD v) {
    if (L > R) return ;
    if (L <= l && r <= R) {
        tag[rt] += v; mx[rt] += v;
        return ;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) update(lson, L, R, v); 
    if (R > mid) update(rson, L, R, v);
    pushup(rt);
}
LD query(int l,int r,int rt,int L,int R) {
    if (L > R) return 0;
    if (L <= l && r <= R) {
        return mx[rt];
    }
    int mid = (l + r) >> 1;
    LD res = -INF;
    if (L <= mid) res = max(res, query(lson, L, R));
    if (R > mid) res = max(res, query(rson, L, R));
    return res;
}
bool check(LD x) {
    LD ans = 0, sum = 0;
    for (int i=1; i<=n; ++i) ta[i] = max((LD)0, x - A[i].w), sum += A[i].w - x;
    for (int i=1; i<=m; ++i) tb[i] = max((LD)0, x - B[i]), sum += B[i] - x;
    build(Root);
    for (int i=1; i<=m+1; ++i) {
        ans = query(Root, 0, i - 1) + tb[i];
        for (int sz=vec[i].size(),j=0; j<sz; ++j) update(Root, 0, A[vec[i][j]].l - 1, ta[vec[i][j]]);
        update(Root, i, i, ans);
    }
    return sum + ans > -eps;
}
int main() {
    n = read(), m = read(), k = read();
    LD L = INF, R = -INF, ans;
    for (int i=1; i<=n; ++i) A[i].w = read(), L = min((LD)A[i].w, L);
    for (int i=1; i<=m; ++i) B[i] = read(), R = max((LD)B[i], R);
    for (int i=1; i<=n; ++i) {
        A[i].l = read(), A[i].r = read();
        vec[A[i].r].push_back(i);
    }
    while (R - L > eps) {
        LD mid = (L + R) / 2.0;
        if (check(mid)) ans = mid, L = mid;
        else R = mid;
    }
    double pr = ans;
    printf("%.10lf",pr);
    return 0;
}

装箱问题

很多个ai，∑ai<=n，问哪些数可以表示出。
将很多个ai合并。
2x+1个a => a, x个2a
2x+2个a => a, a, x个2a。
O(sqrt(n) / 32)

从头开始不断合并。