@2368860385 2020-11-07T03:01:52.000000Z 字数 5532 阅读 145

后：day4

衢州

2018.8.7
考试day4

预计：100+30+0
实际：80+30+13

T1

开始不懂题意，先看T2去了。
写完T2的暴力回来看，然后又看了很长时间才明白题意，而且被样例坑了，及时发现，改正。
挖掘性质：发现赔率只有2n个是可以取的。
然后先写n^2的暴力，枚举两个赔率。
然后在调试过程中，发现好像具有单调性。
调完暴力，打表发现具有单调性，于是写了三分。

一个细节，加号写成减号，少了20分，或者说多了80分。
这个细节使程序不对的。
数据有两个点是这样的。

T2

先想了会儿，写出n^2的暴力。
然后考虑优化，感觉好像是CDQ，线段树。
CDQ发现不行。
想线段树，想了很长时间，其中想了一个做法，（根据自己画的样例想的。。。），开始写了，写了一个多小时，发现不行，然后没有再想到什么解决的方法。
最后的时候发现好像要套个树状数组，有发现但是即使套了也不能做。

思路：set维护出现的位置，然后树状数组单点修改。发现影响的不只是几个点，还是一段区间，而且每个值影响的可能不一样。

T3

T2线段树发现不行的时候，还有1个小时，然后，先过来想T3，没有头绪，又回去开T2，没有办法，又回来看T3，之后想了一个dfs+剪枝的思路，还有不到半个小时，于是开始码，发现细节太多，而且好像还有点问题。最后写完了，不过样例，交了。

数据中有12个m=1的点，然后这样再dfs一调用就推出了，所以就输出了1。
然后有一个答案等于0的点，由于剪枝，没有进入递归，直接返回0。

总结：

1、T2的思路，没证明，没想好，就乱打，想想各种数据，各种情况。
2、时间分配，T3的时间很少（虽然多了可能也没有想法）。
3、T1的细节问题（假设对着一个人，一句一句的讲代码，看一遍，读一遍，想一遍）
4、集中注意力写代码，T2的bug好多。

T1

第38和74行注意是i+1，考试时写成了i-1。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
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 = 1000100;
const double eps = 1e-10;
struct Node{
    double a,p,x,y;
}A[N],B[N];
bool cmp1(Node A,Node B) {
    return A.x < B.x;
}
bool cmp2(Node A,Node B) {
    return A.y < B.y;
}
double sumA[N], sumB[N];
void solve1(int n) {
    double Ans = 0;
    for (int i=1; i<=n; ++i) 
        sumA[i] = sumA[i-1] + A[i].a, sumB[i] = sumB[i-1] + B[i].a;
    for (int i=0; i<=n; ++i) {
        if (A[i].x == A[i+1].x) continue;
        double s1 = sumA[i], s2, t1, t2;
        for (int j=0; j<=n; ++j) {
            if (B[j].y == B[j+1].y) continue;
            s2 = sumB[j];
            t1 = s1 + s2 - s2 * B[j].y;
            t2 = s2 + s1 - s1 * A[i].x;
            //if (min(t1,t2) > Ans) printf("%d %d\n",i,j);
            Ans = max(Ans, min(t1,t2));
        }
    }
    printf("%.6lf",Ans);
}
int main() {
//  freopen("ex_a2.in","r",stdin);
//  freopen("2.txt","w",stdout);
    int n; cin >> n;
    for (int i=1; i<=n; ++i) {
        scanf("%lf%lf",&A[i].a,&A[i].p);
        A[i].x = 1 / A[i].p; // 压A队的赔率最少是。
        A[i].y = 1 / (1.0 - A[i].p); // 压B队的赔率最少是。 
        B[i] = A[i];
    }
    sort(A+1, A+n+1, cmp1);
    sort(B+1, B+n+1, cmp2);
//  solve1(n);return 0;
    if (n <= 5000) { solve1(n); return 0; }
    double Ans = 0;
    for (int i=1; i<=n; ++i) 
        sumA[i] = sumA[i-1] + A[i].a, sumB[i] = sumB[i-1] + B[i].a;
    for (int i=0; i<=n; ++i) {
        if (A[i].x == A[i+1].x) continue;
        double s1 = sumA[i], s2, t1, t2;
        int L = 1,R = n, Lmid, Rmid;
        while (L < R) {
            Lmid = (L + R) / 2;
            Rmid = (Lmid + R) / 2;
            t1 = min(s1 + sumB[Lmid] - sumB[Lmid] * B[Lmid].y, 
                     sumB[Lmid] + s1 - s1 * A[i].x);
            t2 = min(s1 + sumB[Rmid] - sumB[Rmid] * B[Rmid].y, 
                     sumB[Rmid] + s1 - s1 * A[i].x);
            if (t1 >= t2) R = Rmid;
            else L = Lmid;
            Ans = max(Ans,max(t1,t2));
        }
    }
    printf("%.6lf",Ans);
    return 0;
}
/*
3
2 0.5
5 0.1
4 0.9
*/
//  for (int i=1; i<=n; ++i) cout << A[i].a << " " << A[i].p << " " << A[i].x << " " ; puts("");
//  for (int i=1; i<=n; ++i) cout << B[i].a << " " << B[i].p << " " << B[i].y << " " ;
//  for (int i=1; i<=n; ++i) cout << A[i].x << " " ; puts("");
//  for (int i=1; i<=n; ++i) cout << B[i].y << " " ;

T2

每个点i作为右端点的贡献为 $\sum_{j=1}^imax(last[j])$ ，last[i]为i的A[i]的上一个位置。然后就可以 $O(n^2)$ 的复杂度求出答案了。
对于一段区间的答案，有自身的限制（称为限制a），和区间前面的限制（称为限制b）。
对于区间[l,r]的一个点i：自身的限制就是 $\sum_{j=l}^imax(last[j])$ 。前面的限制就是 $\sum_{j=1}^{l-1}max(last[j])$ ，假设在last[j]最大的是位置是P，那么i的答案就是i-P+1。

思想：正难则反

这道题统计非法区间的答案，然后用线段树维护。
这里如果我们统计对于右端点为i的非法区间的答案，就是P
记 $pos[i] = \sum_{j=1}^imax(last[j])$ ，一段区间的pos为这段区间最大的pos，pos[i]在原序列上是递增的。
记 $sum[i]$ 为这段区间内只考虑限制a的答案。
对于区间只有一个数的 $sum[i]$ 就是 $pos[i]$ ，否则考虑它由两段区间合并成一个。

合并的过程：
此时左右区间的限制a已经计算完了（也得到了此时的 $sum$ ，但是合并成一个区间后，右区间限制b可以由左区间来更新，有点像CDQ分治）考虑左区间对右区间的影响。
实际上只考虑只有左区间的 $pos$ 对右区间的影响就好了，因为用限制b来更新右区间时，是取最大的， $pos$ 就是最大的 $last[j]$ ，设左区间的 $pos$ 为 $P$ 。

1、 $P$ >=右区间的 $pos$ ，那么右区间的所有数都受到影响（暴力右区间的所有数扫一遍左区间取最大值的过程中，而左区间的 $last$ 的最大值比右区间的所有的大，所以都会受到影响），然后更新 $sum[rt] = sum[lc] + (r-m)*pos[lc]$ 。
2、否则：因为 $pos$ 是整个区间最大的，所以右区间的前部分还是可能比 $P$ 小的，受到左区间的影响的。
重新计算右区间受左区间的影响的答案。
如何计算：
对整个右区间递归处理。 $pos[i]$ 是递增的，受到影响的是一个右区间的一个前缀。
（以下的左右区间为当前的左右区间）
那么还是先考虑P是否大于 $pos[lc]$ （当前区间的左区间），如果大于，左区间全部收到影响，然后递归右区间就好了。
否则左区间的一部分受到影响，递归左区间，直接加上右区间的答案。
此时右区间的答案不是 $sum[rc]$ ，是 $sum[rt]-sum[lc]$ 。回顾 $sum$ 的定义，只考虑限制a，所以 $sum[rc]$ 就是只有它自己的限制，但是此时要求整个区间的 $sum$ ，应该有左区间对右区间的限制。
或者这样理解：原来此区间答案为 $sum[rt]$ ，此时区间的前一部分（不超过左区间的长度，就是左区间的一部分）受到了P的影响，那么左区间就重新计算了，那么新的答案就是 $sum[rt]-sum[lc]+calc(左区间)$ 。先减去以前的答案，在加上新计算完了的答案。

为每个值建一个set，记录这个值的所有位置， $logn$ 找到更新的位置。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
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 = 100100;
int lastv[N], last[N], A[N], pos[N << 2];
LL sum[N << 2];
set<int> s[N];
set<int> :: iterator pre, nxt;
int n;
#define Root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1
LL Calc(int l,int r,int rt,int P) { // 重新计算右区间受到左区间影响后的答案 
    if (l == r) return max(pos[rt], P);
    int mid = (l + r) >> 1;
    if (pos[lc] < P) return 1ll * (mid - l + 1) * P + Calc(rson, P);
    else return sum[rt] - sum[lc] + Calc(lson, P);
}
void pushup(int l,int r,int mid,int rt) { // 合并区间 
    if (pos[lc] >= pos[rc]) 
        pos[rt] = pos[lc], sum[rt] = sum[lc] + 1ll * (r - mid) * pos[lc];
    else 
        pos[rt] = pos[rc], sum[rt] = sum[lc] + Calc(mid + 1, r, rc, pos[lc]);
}
void build(int l,int r,int rt) {
    if (l == r) {
        sum[rt] = pos[rt] = last[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson); build(rson);
    pushup(l, r, mid, rt);
}
void update(int l,int r,int rt,int p,int v) {
    if (l == r) {
        sum[rt] = pos[rt] = v;
        return ;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(lson, p, v);
    else update(rson, p, v);
    pushup(l, r, mid, rt);
}
void work(int p,int v) {
    pre = s[A[p]].lower_bound(p), --pre;
    nxt = s[A[p]].upper_bound(p);
    if (nxt != s[A[p]].end()) update(Root, *nxt, *pre);
    s[A[p]].erase(p);
    pre = nxt = s[v].upper_bound(p), --pre;
    s[v].insert(p), update(Root, p, *pre);
    if (nxt != s[v].end()) update(Root, *nxt, p);
    A[p] = v;
}
int main() {
    n = read();
    for (int i=1; i<=n; ++i) s[i].insert(0);
    for (int i=1; i<=n; ++i) {
        A[i] = read();
        last[i] = lastv[A[i]];
        lastv[A[i]] = i;
        s[A[i]].insert(i);
    }
    build(Root);
    LL tot = 1ll * n * (n + 1) / 2;
    for (int Q=read(); Q--; ) {
        int opt = read();
        if (!opt) printf("%lld\n",tot - sum[1]);
        else {
            int p = read(), v = read();
            work(p, v);
        }
    }
    return 0;
}

后：day4

T1

T2

T3

T1

T2

内容目录