历史研究（ JOISC 2014 Day1 T2）

佚名 6年前 (2019-04-11) 随笔 489人围观抢沙发百度已收录

历史研究（ JOISC 2014 Day1 T2）

题目描述

IOI 国历史研究的大牛——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。
日记中记录了连续 \(N\)天发生的事件，每天发生一件事件。
事件有种类之分。第 \(i\) 天发生的事件的种类用一个整数 \(X_i\) 表示，\(X_i\) 越大，事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记：

选择日记中连续的一些天作为分析的时间段；
事件种类 \(t\) 的重要度为 t\(\times\)(这段时间内重要度为 \(t\) 的事件数)；
计算出所有事件种类的重要度，输出其中的最大值。

请制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入

第一行两个空格分隔的整数 \(N\) 和 \(Q\)，表示日记一共记录了 \(N\) 天，询问有 \(Q\) 次。
接下来一行 \(N\) 个空格分隔的整数 \(X_1\dots X_N\)，\(X_i\) 表示第 \(i\) 天发生的事件的种类。
接下来 \(Q\) 行，第 \(i\) 行有两个空格分隔整数 \(A_i\) 和 \(B_i\)，表示第 \(i\) 次询问的区间为 \([A_i,B_i]\)。

输出

输出 \(Q\) 行，第 \(i\) 行一个整数，表示第 \(i\) 次询问的最大重要度。

思路

这题暴力应该都会写，离散后\(O(n^2)\)就可以解决.

struct Pt1{
    int sum[N];
    void solve(){
        while(q--){
            int l,r;
            sf("%d%d",&l,&r);
            FOR(i,1,n)cnt[i]=0;
            ll mx=0;
            FOR(i,l,r){
                cnt[a[i]]++;
                ll sum=1ll*b[a[i]]*cnt[a[i]];
                if(mx<sum)mx=sum;
            }
            pf("%lld\n",mx);
        }
    }
}Pt_1;

不过如果要进一步优化，显然考虑能否能避免一些重复计算过的一些区间，或者，限制一下需要循环计算的区间呢？

使用莫队！！！

考虑分块，将所有询问放在左端点的所在的块编号上，然后再将所有的在同一块中的区间进行右端点排序，然后，若是右端点也在同一个块内，就直接扫过去计算，对于右端点在块外的点，用一个指针向右推过去计算过去，将在块外的区间放在另一个变量里进行维护，每次将指针不断向右推因为右端点是不断增大的（之前排过序了），那么这样可以保证块外的点最多被计算到一次。

那么综合以上部分，便可以在\(O(n*sqr(n))\) 内算出答案。

对于那些对复杂度有疑问的嘛。。

右指针最多移动 \(n\) 次,总移动次数变为\(K * n\).

至于每次块内的计算，就算每次跑满，总移动次数为\(Q* n / K\)

\(K\)也就是\(sqr(n)\)，那么就是\(n*sqr(n)\)

代码

#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l),i##END=(r);i<=i##END;i++)
#define DOR(i,r,l) for(int i=(r),i##END=(l);i>=i##END;i--)
#define loop(i,n) for(int i=0,i##END=(n);i<i##END;i++)
#define sf scanf
#define pf printf
#define pb push_back
#define mms(a,x) memset(a,x,sizeof a)
using namespace std;
typedef long long ll;
typedef long double db;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int N=1e5+5;
int n,q,S;
int a[N],b[N],cnt[N],ct=0;
struct Pt1{
    int sum[N];
    void solve(){
        while(q--){
            int l,r;
            sf("%d%d",&l,&r);
            FOR(i,1,n)cnt[i]=0;
            ll mx=0;
            FOR(i,l,r){
                cnt[a[i]]++;
                ll sum=1ll*b[a[i]]*cnt[a[i]];
                if(mx<sum)mx=sum;
            }
            pf("%lld\n",mx);
        }
    }
}Pt_1;
struct Pt2{
    struct Query{
        int l,r,id;
        bool operator<(const Query &A)const{return r<A.r;}
    };
    vector<Query>Q[N];
    ll sum[N],ans[N];
    void solve(){
        S=sqrt(n);if(!S)S=1;
        FOR(i,1,q){
            int l,r;
            sf("%d%d",&l,&r);
            Q[l/S].pb((Query){l,r,i});
        }
        FOR(i,0,n/S){
            if(Q[i].empty())continue;
            int r=(i+1)*S-1;
            sort(Q[i].begin(),Q[i].end());
            FOR(j,1,ct)sum[j]=0;
            int cur=r;
            ll mx=0,mxr=0;
            loop(j,Q[i].size()){
                Query P=Q[i][j];
                if(P.r<=r){
                    mx=0;
                    FOR(k,P.l,P.r){
                        sum[a[k]]+=b[a[k]];
                        chkmax(mx,sum[a[k]]);
                    }
                    FOR(k,P.l,P.r)sum[a[k]]-=b[a[k]];
                }
                else{
                    while(cur<P.r){
                        cur++;sum[a[cur]]+=b[a[cur]];
                        chkmax(mxr,sum[a[cur]]);
                    }mx=mxr;
                    FOR(k,P.l,r){
                        sum[a[k]]+=b[a[k]];
                        chkmax(mx,sum[a[k]]);
                    }
                    FOR(k,P.l,r)sum[a[k]]-=b[a[k]];
                }
                ans[P.id]=mx;
            }
        }
        FOR(i,1,q)pf("%lld\n",ans[i]);
    }
}Pt_2;
int main(){
    freopen("history.in","r",stdin);
    freopen("history.out","w",stdout);
    sf("%d%d",&n,&q);
    FOR(i,1,n){
        sf("%d",&a[i]);
        b[i]=a[i];
    }
    ct=n;sort(b+1,b+ct+1);
    ct=unique(b+1,b+ct+1)-b-1;
    FOR(i,1,n)a[i]=lower_bound(b+1,b+ct+1,a[i])-b;
    Pt_2.solve();
    return 0;
}