CF773E Blog Post Rating

87 阅读 0 评论 58 点赞

我是靠谱客的博主追寻流沙，最近开发中收集的这篇文章主要介绍CF773E Blog Post Rating，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：有一篇博客。一共有n个人，心中有他们期望该博客得到的赞数a[i]。当某个时刻该博客的获赞数<a[i]，则该人会使得赞数+1，当赞数>a[i]，该人会使得赞数-1，当赞数=a[i]，不做任何改变。

对于1<=k<=n，询问1~k个人按一定的顺序给该博客从0开始点赞或点踩，该博客的最大获赞数。

-1e5<=a[i]<=1e5,n<=1e5。

标程：

 1 #include<bits/stdc++.h>
 2 #define mid ((l+r)>>1)
 3 using namespace std;
 4 const int N=500002;
 5 const int inf=0x3f3f3f3f;
 6 int tag1[N<<3],tag2[N<<3],Max[N<<3],Min[N<<3],n,ax;
 7 
 8 void build1(int k,int l,int r)
 9 {
10     if (l==r) {Max[k]=l;return;}
11     build1(k<<1,l,mid);build1(k<<1|1,mid+1,r);
12     Max[k]=max(Max[k<<1],Max[k<<1|1]);
13 }
14 void build2(int k,int l,int r)
15 {
16     if (l==r) {Min[k]=l;return;}
17     build2(k<<1,l,mid);build2(k<<1|1,mid+1,r);
18     Min[k]=min(Min[k<<1],Min[k<<1|1]);
19 }
20 void down1(int k)
21 {
22     if (tag1[k])
23     {
24         tag1[k<<1]+=tag1[k],tag1[k<<1|1]+=tag1[k];
25         Max[k<<1]+=tag1[k],Max[k<<1|1]+=tag1[k];
26         tag1[k]=0;
27     }
28 }
29 void down2(int k)
30 {
31     if (tag2[k])
32     {
33         tag2[k<<1]+=tag2[k],tag2[k<<1|1]+=tag2[k];
34         Min[k<<1]+=tag2[k],Min[k<<1|1]+=tag2[k];
35         tag2[k]=0;
36     }
37 }
38 void add1(int k,int l,int r,int x)
39 {
40    if (x<=l) {tag1[k]++;Max[k]++;return;}
41    down1(k);
42    if (x<=mid) add1(k<<1,l,mid,x);
43    add1(k<<1|1,mid+1,r,x);
44    Max[k]=max(Max[k<<1],Max[k<<1|1]);
45 }
46 void add2(int k,int l,int r,int x)
47 {
48     if (r<=x) {tag2[k]++;Min[k]++;return;}
49     down2(k);
50     if (x>mid) add2(k<<1|1,mid+1,r,x);
51     add2(k<<1,l,mid,x);
52     Min[k]=min(Min[k<<1],Min[k<<1|1]);
53 }
54 int qry1(int k,int l,int r)//找到恰好为0的位置 
55 {
56     if (l==r) return l;
57     down1(k);
58     if (Max[k<<1]>=0) return qry1(k<<1,l,mid);
59     else return qry1(k<<1|1,mid+1,r);
60 }
61 int qry2(int k,int l,int r,int x)
62 {
63     if (x<=l) return Min[k];
64     down2(k); int res=inf;
65     if (x<=mid) res=min(res,qry2(k<<1,l,mid,x));
66     res=min(res,qry2(k<<1|1,mid+1,r,x));
67     return res;
68 }
69 int main()
70 {
71     build1(1,-N,0);
72     build2(1,-N,N);
73     scanf("%d",&n);
74     for (int i=1;i<=n;i++)
75     {
76         scanf("%d",&ax);
77         if (ax<0) add1(1,-N,0,ax);
78         add2(1,-N,N,ax-1);
79         int l=qry1(1,-N,0);
80         printf("%dn",qry2(1,-N,N,l));
81     }
82     return 0;
83 }