ATcoder就是天下第一大毒瘤.....总是会在输出上卡死你...
之前因为换行而没过，这回TM是没换行没过...毒瘤致死。
题意：多次求区间内一个数的出现次数与自己值的乘积的最大值。
解：莫队。
发现删除操作很不好搞，干脆不删除了。
那么对于每个块，所有左端点在该块内的询问，右端点是单增的。这个显然没有删除。
左端点我们每次都暴力加就行了。总时间复杂度还是n1.5。
具体来说，我们先暴力处理两端点都在这个块内的询问，对于接下来的询问，先把右端点搞好，然后记录答案。
暴力加左端点。记录答案，之后还原。
参考代码实现。
1 #include2 #include 3 #include 4 #include 5 6 typedef long long LL; 7 const int N = 100010; 8 9 int fr[N], a[N], bin[N], X[N], bin2[N]; 10 LL ans; 11 12 struct ASK { 13 int l, r, t; 14 LL ans; 15 inline bool operator <(const ASK &w) const { 16 if(fr[l] != fr[w.l]) { 17 return l < w.l; 18 } 19 return r < w.r; 20 } 21 }ask[N]; 22 23 inline bool cmp(const ASK &A, const ASK &B) { 24 return A.t < B.t; 25 } 26 27 inline void add(int x) { 28 bin[a[x]]++; 29 ans = std::max(ans, 1ll * bin[a[x]] * X[a[x]]); 30 return; 31 } 32 33 inline void del(int x) { 34 bin[a[x]]--; 35 return; 36 } 37 38 int main() { 39 int n, q; 40 scanf("%d%d", &n, &q); 41 int T = sqrt(n); 42 for(int i = 1; i <= n; i++) { 43 scanf("%d", &a[i]); 44 fr[i] = (i - 1) / T + 1; 45 X[i] = a[i]; 46 } 47 for(int i = 1; i <= q; i++) { 48 scanf("%d%d", &ask[i].l, &ask[i].r); 49 ask[i].t = i; 50 } 51 std::sort(ask + 1, ask + q + 1); 52 std::sort(X + 1, X + n + 1); 53 int temp = std::unique(X + 1, X + n + 1) - X - 1; 54 for(int i = 1; i <= n; i++) { 55 a[i] = std::lower_bound(X + 1, X + temp + 1, a[i]) - X; 56 } 57 58 for(int i = 1; i <= q; ) { 59 if(fr[ask[i].l] != fr[ask[i - 1].l]) { // new 60 memset(bin, 0, sizeof(bin)); 61 ans = 0; 62 int p = fr[ask[i].l]; 63 for(; p == fr[ask[i].r]; i++) { 64 for(int j = ask[i].l; j <= ask[i].r; j++) { 65 add(j); 66 } 67 ask[i].ans = ans; 68 for(int j = ask[i].l; j <= ask[i].r; j++) { 69 del(j); 70 } 71 ans = 0; 72 } 73 int l = p * T; 74 int r = l + 1; 75 add(r); 76 LL lastans; 77 for(; fr[ask[i].l] == p; i++) { 78 while(r < ask[i].r) { 79 add(++r); 80 } 81 lastans = ans; 82 for(int j = ask[i].l; j <= l; j++) { 83 add(j); 84 } 85 ask[i].ans = ans; 86 ans = lastans; 87 for(int j = ask[i].l; j <= l; j++) { 88 del(j); 89 } 90 } 91 } 92 } 93 94 std::sort(ask + 1, ask + q + 1, cmp); 95 for(int i = 1; i <= q; i++) { 96 printf("%lld\n", ask[i].ans); 97 } 98 99 return 0;100 }