[hdoj5192] 树状数组

枚举所有的区间。对于确定的区间，假设最终的高度为h，
代价是
代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <map>
  6 #include <queue>
  7 #include <cmath>
  8 #include <vector>
  9 #include <ctime>
 10 #include <cctype>
 11 
 12 using namespace std;
 13 
 14 #define mem0(a) memset(a, 0, sizeof(a))
 15 #define lson l, m, rt << 1
 16 #define rson m + 1, r, rt << 1 | 1
 17 #define define_m int m = (l + r) >> 1
 18 #define Rep(a, b) for(int a = 0; a < b; a++)
 19 #define lowbit(x) ((x) & (-(x)))
 20 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
 21 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
 22 
 23 typedef double db;
 24 typedef long long LL;
 25 
 26 const int dx[4] = {1, 0, -1, 0};
 27 const int dy[4] = {0, -1, 0, 1};
 28 const int maxn = 1e4 + 7;
 29 const int maxm = 1e5 + 7;
 30 const int MD = 1e9 +7;
 31 
 32 struct Point {
 33     int x, y;
 34     bool operator < (const Point &opt) const {
 35         return x < opt.x || x == opt.x && y < opt.y;
 36     }
 37     Point operator - (const Point &opt) const {
 38         return Point(x - opt.x, y - opt.y);
 39     }
 40     constructInt2(Point, x, y);
 41     void inp() {
 42         scanf("%d %d", &x, &y);
 43     }
 44     void outp() {
 45         printf("(%d, %d), ", x, y);
 46     }
 47 };
 48 
 49 struct Trie {
 50         const static int char_size = 26;
 51         int cc;
 52         int cht[100010][char_size];
 53         int mark[100010];
 54         Trie() { cc = 0; mem0(mark); mem0(cht); }
 55         int Idex(char ch) { return ch - '0'; }
 56         void Insert(char s[], int v) {
 57                 int pos = 0;
 58                 for(int i = 0; s[i]; i++) {
 59                         int id = Idex(s[i]);
 60                         if(!cht[pos][id]) cht[pos][id] = ++cc;
 61                         pos = cht[pos][id];
 62                 }
 63                 mark[pos] = v;
 64         }
 65         bool Find(char s[]) {
 66                 int pos = 0;
 67                 for(int i = 0; s[i]; i++) {
 68                         int id = Idex(s[i]);
 69                         if(!cht[pos][id]) return 0;
 70                         pos = cht[pos][id];
 71                 }
 72                 return mark[pos];
 73         }
 74 };
 75 
 76 struct KMP {
 77         int next[1000010];
 78         void GetNext(char s[]) {
 79                 mem0(next);
 80                 next[0] = next[1] = 0;
 81                 for(int i = 1; s[i]; i++) {
 82                         int j = next[i];
 83                         while(j && s[i] != s[j]) j = next[j];
 84                         next[i + 1] = s[j] == s[i]? j + 1 : 0;
 85                 }
 86         }
 87         void Match(char s[], char t[]) {
 88                 int j = 0, len = strlen(t);
 89                 for(int i = 0; s[i]; i++) {
 90                         while(j && s[i] != t[j]) j = next[j];
 91                         if(s[i] == t[j]) j++;
 92                         if(j == len) printf("%d
", i - len + 1);
 93                 }
 94         }
 95 };
 96 
 97 struct Matrix {
 98         int a[3][3];
 99         Matrix operator * (const Matrix &_A) const {
100                 Matrix tmp;
101                 mem0(tmp.a);
102                 for(int i = 0; i < 3; i++) {
103                         for(int j = 0; j < 3; j++) {
104                                 for(int k = 0; k < 3; k++) {
105                                         tmp.a[i][j] = ((LL)a[i][k] * _A.a[k][j] + tmp.a[i][j]) % MD;
106                                 }
107                         }
108                 }
109                 return tmp;
110         }
111 };
112 
113 struct Edge {
114     int u, v;
115     constructInt2(Edge, u, v);
116 };
117 
118 struct Segment {
119         Point a, b;
120         void inp() {
121                 scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
122                 if(a.x > b.x) {
123                         swap(a.x, b.x);
124                         swap(a.y, b.y);
125                 }
126         }
127 };
128 
129 Matrix CalcMatrix(Matrix a, int n) {
130         if(n == 1) return a;
131         Matrix tmp = CalcMatrix(a, n >> 1);
132         tmp = tmp * tmp;
133         if(n & 1) tmp = tmp * a;
134         return tmp;
135 }
136 
137 inline int ReadInt() {
138     char c = getchar();
139     while(!isdigit(c)) c = getchar();
140 
141     int x = 0;
142     while(isdigit(c)) {
143         x = x * 10 + c - '0';
144         c = getchar();
145     }
146     return x;
147 }
148 
149 inline void WriteInt(int i) {
150     int p = 0;
151     static int buf[10];
152     if(i == 0) p++;
153     else while(i) {
154         buf[p++] = i % 10;
155         i /= 10;
156     }
157     for(int j = p - 1; j; j--) putchar('0' + buf[j]);
158 }
159 
160 int Cross(Point a, Point b) {
161     return a.x * b.y - a.y * b.x;
162 }
163 
164 int Dist2(Point a, Point b) {
165     int x = a.x - b.x, y = a.y - b.y;
166     return x * x + y * y;
167 }
168 int ConvexHull(Point *p, int n, Point *ch) {
169     sort(p, p + n);
170     int m = 0;
171     for (int i = 0; i < n; i++) {
172         while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
173         ch[m++] = p[i];
174     }
175     int k = m;
176     for (int i = n - 2; i >= 0; i--) {
177         while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
178         ch[m++] = p[i];
179     }
180     if (n > 1) m--;
181     return m;
182 }
183 
184 template<class edge> struct Graph {
185     vector<vector<edge> > adj;
186     Graph(int n) { adj.clear(); adj.resize(n + 5); }
187     Graph() { adj.clear(); }
188     void resize(int n) { adj.resize(n + 5); }
189     void add(int s, edge e){ adj[s].push_back(e); }
190     void del(int s, edge e) { adj[s].erase(find(iter(adj[s]), e)); }
191     void clear() { adj.clear(); }
192     vector<edge>& operator [](int t) { return adj[t]; }
193 };
194 
195 template<class T> struct TreeArray {
196     vector<T> c;
197     int maxn;
198     TreeArray(int n) { c.resize(n + 5); maxn = n; }
199     TreeArray() { c.clear(); maxn = 0; }
200     void clear() { memset(&c[0], 0, sizeof(T) * maxn); }
201     void resize(int n) { c.resize(n + 5); maxn = n; }
202     void add(int p, T x) { while (p < maxn) { c[p] += x; p += lowbit(p); } }
203     T get(int p) { T res = 0; while (p) { res += c[p]; p -= lowbit(p); } return res; }
204     T range(int a, int b) { return get(b) - get(a - 1); }
205 };
206 
207 int n, W, H, a[160000];
208 LL sum[160000], step, maxh;
209 TreeArray<LL> ta(50001), ta0(50001);
210 void Check(int h, int r) {
211     if (sum[n + 2 * W - 1] < (LL)h * W) return ;
212     LL sum1 = ta0.get(h + 1), sumall = sum[r] - sum[r - W], c = ta.get(h + 1);
213     LL newsum1 = h * c - sum1, newsum2 = sumall - h * W + newsum1;
214     LL res = max(newsum1, newsum2);
215     if (res < step || res == step && h > maxh) {
216         step = res;
217         maxh = h;
218     }
219 }
220 int main() {
221     //freopen("in.txt", "r", stdin);
222     while (cin >> n >> W >> H) {
223         mem0(a);
224         for (int i = 0; i < n; i++) {
225             scanf("%d", a + i + W);
226         }
227         int total = n + 2 * W;
228         for (int i = 1; i < total; i++) sum[i] = sum[i - 1] + a[i];
229 
230         if (sum[total - 1] < (LL)H * W) {
231             puts("-1");
232             continue;
233         }
234 
235         ta.clear();
236         ta0.clear();
237         step = H * W;
238         maxh = H;
239         ta.add(1, W );
240         ta0.add(1, 0);
241 
242         for (int i = W; i < total; i++) {
243             int num = sum[i] - sum[i - W], ave = num / W;
244             if (ave < H) ave = H;
245             ta.add(a[i - W] + 1, -1);
246             ta0.add(a[i - W] + 1, -a[i - W]);
247             ta.add(a[i] + 1, 1);
248             ta0.add(a[i] + 1, a[i]);
249             Check(ave, i);
250             Check(ave + 1, i);
251         }
252         cout << maxh << " " << step << endl;
253     }
254     return 0;
255 }

View Code