4241: Historical Studies

Time Limit: 80 Sec Memory Limit: 512 MB
Description

Professor JOI, the first person to study the history of IOI, recently obtained a diary written by the inhabitants of an ancient IOI country. In order to study the life of ancient IOI countries, Professor JOI began to investigate the events recorded in his diary.
The diary records the time of N consecutive days, about one occurrence per day.
There are different kinds of events. The type of events on day i (1 <= i <= N) is expressed by an integer Xi. The larger the Xi, the larger the scale of the events.
Professor JOI decided to analyze these diaries in the following way:
1. Choose consecutive days in the diary as the time period for analysis.
2. The importance of event type T is t* (the number of events whose importance is t in this period)
3. Calculate the importance of all kinds of events and output the maximum of them.
Now you're asked to create a program to help professors analyze, and each time you give an interval of analysis, you need to output the maximum of importance.
4.
Input

In the first line, the integers N and Q separated by two spaces indicate that the diary records a total of N days and Q queries.
Next line N spaces separated integer X1... XN, Xi denotes the type of events that occurred on day i

Output

Output line Q, line I (1<=i<=Q) an integer, indicating the greatest importance of the first query

Sample Input

5 5

9 8 7 8 9

1 2

3 4

4 4

1 4

2 4

Sample Output

9

8

8

16

16

HINT

1<=N<=10^5

1<=Q<=10^5

1<=Xi<=10^9 (1<=i<=N)

Main idea of the title:
There is a sequence of length n.
There are m queries. Each query multiplies the maximum number of occurrences of each value in the l~r range.

Ideas:
It sounds absurd to roll back to Momo.
Rolling back the Mo team can replace the deletion operation and keep the time complexity at O (nsqrtn).
Blocking and sorting are done according to Kimo Team In practice, and then when counting the answers, if the left and right endpoints of a query are in the same block, then violence statistics.
Then for the left endpoint in the same block, we count together, first let the left endpoint in the right end of the block, and then let the right endpoint expand normally to the right. When the right endpoint meets the requirement, record the state at this time, then adjust the left endpoint to the left endpoint of the query, then count the answers, and then roll back to the state when the left endpoint is not adjusted. Then make the next inquiry.
Mo Team... It's really a good way to use card violence.

#include <cstdio>
#include <cstring>
#include <cmath> 
#include <algorithm>
#define N 120000
#define LL long long
using namespace std;

int n, m, block, pos;
int a[N], aa[N], place[N], top;
LL sum[N], num[N], pre, now, ans[N];

struct Query{
    int l, r, id;
}q[N];

bool cmp ( Query aa, Query bb ){//In block r，Out of block l 
    return place[aa.l] < place[bb.l] || (place[aa.l] == place[bb.l] && aa.r < bb.r); 
}

void adde(int c){
    sum[c] += aa[c];//+-Yes. aa The original value in 
    now = max(now, sum[c]);
}

void del(int c){
    sum[c] -= aa[c];
}

int main(){
    scanf("%d%d", &n, &m);
    block = (int) sqrt(n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        aa[i] = a[i];
    }
    sort(aa+1, aa+1+n);
    top = unique(aa+1, aa+1+n) - aa;//Duplicate removal 
    for(int i=1; i<=n; i++)
        a[i] = lower_bound(aa+1, aa+top, a[i]) - aa;//Discretization 
    for(int i=1; i<=m; i++){
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;//querysort 
    }
    for(int i=1; i<=n; i++)
        place[i] = (i-1) / block + 1;
    sort(q+1, q+1+m, cmp);
    int l, r;
    for(int i=1; i<=m; i++){
        if(place[q[i].l] != place[q[i-1].l]){
            memset(sum, 0, sizeof(sum));
            pre = now = 0;
            l = pos = place[q[i].l] * block + 1;//lPut it on the left end of the block 
            r = l - 1;//Guarantee that the initial value is zero 
        }
        if(place[q[i].l] == place[q[i].r]){//l，r In the same block, do not move l，r violence query 
            LL cur = 0;
            for(int j=q[i].l; j<=q[i].r; j++){
                num[a[j]] += aa[a[j]];
                cur = max(cur, num[a[j]]);
            }
            for(int j=q[i].l; j<=q[i].r; j++)//reduction 
                num[a[j]] -= aa[a[j]];
            ans[q[i].id] = cur;
            continue;

        }
        while(r < q[i].r) adde( a[++r] );//Adding information 
        pre = now;//Record current status 
        while(l > q[i].l) adde( a[--l] );
        ans[q[i].id] = now;//Record answers 
        while(l < pos) del( a[l++] );//Reduction (rollback) 
        now = pre;
    }
    for(int i=1; i<=m; i++) 
        printf("%lld\n", ans[i]);
    return 0;
}