ZOJ 5332 Calculation(离线 + 线段树)

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5332

比赛的时候没有做出来，赛后看了官方题解，虽然各种orz但是依旧只能orz(标程写得真是犀利),然后可耻的到网上找了下题解。。。

做法是线段树 + 离线搞，网上那种对于[l, r]中的l从大到小排序很精妙(有一篇竟然说是以r为关键字,,,然后代码里面却是l。。。汗)，再注意到gcd()对于每一个起点来说，是单调递减的，这样可以乱搞了...

如果还不是很明白，搜下其他的blog吧，他们写得很丰富。。

贴贴代码，，可耻滚粗。

ps .... zoj为何有时能过有时候又被卡了。。。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 //#include <cmath>
  6 
  7 using namespace std;
  8 #define lson rt<<1, l, mid
  9 #define rson rt<<1|1, mid+1, r
 10 typedef pair<int, int> PII;
 11 //typedef __int64 lld;
 12 typedef long long lld;
 13 const int MAXN = 100005;
 14 
 15 struct Q {
 16     int l, r, id;
 17     Q() {}
 18     Q(int a, int b, int c):l(a), r(b), id(c) {}
 19     bool operator < (const Q& cmp) const {
 20         return l > cmp.l;
 21     }
 22 };
 23 vector<Q> GS[55];
 24 int a[MAXN];
 25 lld sum[MAXN << 2];
 26 lld add[MAXN << 2];
 27 int n, m, q;
 28 lld out[MAXN];
 29 int log2[MAXN];
 30 
 31 struct RMQ {
 32     int a[MAXN][22];
 33     void init(int A[], int N) {
 34         for (int i = 1; i <= N; i++) a[i][0] = A[i];
 35         for (int j = 1; (1 << j) <= N; j++) {
 36             for (int i = 1; i + (1<<j) - 1 <= N; i++) {
 37                 a[i][j] = __gcd(a[i][j-1], a[i + (1<<(j-1))][j - 1]);
 38             }
 39         }
 40     }
 41     int rmq(int L, int R) {
 42       //  if (R < L) while (1);
 43         if (R < L) return 0;
 44         int k = log2[R - L + 1];
 45         return __gcd(a[L][k], a[R-(1<<k)+1][k]);
 46     }
 47 }AC;
 48 
 49 /*     *segment tree*    */
 50 void build() {
 51     memset(add, 0, sizeof(add));
 52     memset(sum, 0, sizeof(sum));
 53 }
 54 void Down(int rt, int l, int r) {
 55     if (add[rt]) {
 56         int mid = r + l >> 1;
 57         add[rt<<1] += add[rt];
 58         add[rt<<1|1] += add[rt];
 59         sum[rt<<1] += (lld)(mid - l + 1) * add[rt];
 60         sum[rt<<1|1] += (lld)(r - mid) * add[rt];
 61         add[rt] = 0;
 62     }
 63     return ;
 64 }
 65 void Up(int rt) {
 66     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 67 }
 68 void update(int rt, int l, int r, int L, int R) {
 69     if (L > R) return ;
 70     if (l >= L && r <= R) {
 71         add[rt] += 1;
 72         sum[rt] += r - l + 1;
 73         return ;
 74     }
 75     Down(rt, l, r);
 76     int mid = r + l >> 1;
 77     if (mid >= L) update(lson, L, R);
 78     if (R > mid) update(rson, L, R);
 79     Up(rt);
 80 }
 81 lld query(int rt, int l, int r, int L, int R) {
 82     if (L > R) return 0LL;
 83     if (l >= L && r <= R) {
 84         return sum[rt];
 85     }
 86     Down(rt, l, r);
 87     int mid = r + l >> 1;
 88     lld ret = 0;
 89     if (mid >= L) ret += query(lson, L, R);
 90     if (R > mid) ret += query(rson, L, R);
 91     return ret;
 92 }
 93 /*     *segment tree*    */
 94 
 95 PII arr[MAXN];
 96 void solve(vector<Q> vec, int M) {
 97     sort(vec.begin(), vec.end());
 98     build();
 99     int l = 1, r = 1;
100     for (int i = 1; i <= n; i++) {
101         if (a[i] % M != 0 || AC.rmq(i, n) % M == 0 && AC.rmq(i, n) > M) {
102             arr[i] = make_pair(-1, -1);
103         }else {
104             l = max(l, i); //r = max(r, i);
105             while (l <= n && AC.rmq(i, l) % M == 0 && AC.rmq(i, l) > M) ++ l;
106             r = max(l, r);
107             while (r+1 <= n && AC.rmq(i, r+1) == M) ++ r;
108             if (AC.rmq(i, l) == M) {
109                 arr[i] = make_pair(l, r);
110             }else {
111                 arr[i] = make_pair(-1, -1);
112             }
113         }
114     }
115     int now = n, siz = vec.size();
116     for (int i = 0; i < siz; i++) {
117         Q e = vec[i];
118         while (now >= 1 && e.l <= now) {
119             if (arr[now].first != -1) {
120                 update(1, 1, n, max(1, arr[now].first), arr[now].second);
121             }
122             -- now;
123         }
124         out[e.id] = query(1, 1, n, e.l, e.r);
125     }
126 }
127 /*
128 
129 4 4 4
130 1 2 3 4
131 1 2 3 4
132 0 4 1
133 0 4 2
134 0 4 3
135 0 4 4
136 
137 4 4 4
138 1 2 3 4
139 1 2 3 4
140 0 4 1
141 0 4 2
142 0 2 1
143 3 4 4
144 
145 */
146 
147 int gs[55];
148 int main() {
149     for (int i = 0; i < MAXN; i++) {
150         log2[i] = (i == 0 ? -1 : log2[i >> 1] + 1);
151     }
152     while (scanf("%d%d%d", &n, &m, &q) == 3) {
153         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
154         AC.init(a, n);
155         for (int i = 0; i < m; i++) scanf("%d", &gs[i]);
156         sort(gs, gs + m);
157         for (int i = 0; i < m; i++) GS[i].clear();
158         for (int i = 1; i <= q; i++) {
159             int l, r, x;
160             scanf("%d%d%d", &l, &r, &x);
161             x = lower_bound(gs, gs + m, x) - gs;
162             GS[x].push_back(Q(l + 1, r, i));
163         }
164         for (int i = 0; i < m; i++) {
165             solve(GS[i], gs[i]);
166         }
167         for (int i = 1; i <= q; i++) printf("%lld
", out[i]);
168     }
169     return 0;
170 }

View Code