不难理解,就是为什么要分块呢?

 一种直观的办法是按照左端点排序,再按照右端点排序。但是这样的表现不好。特别是面对精心设计的数据,这样方法表现得很差。

  举个例子,有6个询问如下:(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。

  这个数据已经按照左端点排序了。用上述方法处理时,左端点会移动6次,右端点会移动移动98+97+95+98+95=483次。右端点大幅度地来回移动,严重影响了时间复杂度——排序的复杂度是O(mlogm),所有左端点移动次数仅为为O(n),但右端点每个询问移动O(n),共有m个询问,故总移动次数为O(nm),移动总数为O(mlogm + nm)。运行时间上界并没有减少。

  其实我们稍微改变一下询问处理的顺序就能做得更好:(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。

  左端点移动次数为2+2+1+2+2=9次,比原来稍多。右端点移动次数为2+3+95+3+1=104,右端点的移动次数大大降低了。

上面的过程启发我们:①我们不应该严格按照升序排序,而是根据需要灵活一点的排序方法;②如果适当减少右端点移动次数,即使稍微增多一点左端点移动次数,在总的复杂度上看,也是划算的。

#include<bits/stdc++.h>
typedef long long ll;
const int maxn=5e4+50;
using namespace std;
struct Node{
    ll a,b;
    int l,r,id;
}ask[maxn];
int arr[maxn],pos[maxn];
ll s[maxn],ans;
int cmp_1(Node a,Node b){
    return pos[a.l]==pos[b.l]?a.r<b.r : pos[a.l]<pos[b.l];
}
int cmp_2(Node a,Node b){
    return a.id<b.id;
}
void update(int p,int val){
    ans-=s[arr[p]]*s[arr[p]];
    s[arr[p]]+=val;
    ans+=s[arr[p]]*s[arr[p]];
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    int block=int(sqrt(n));
    for(int i=1;i<=n;i++)
        pos[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&ask[i].l,&ask[i].r);
        ask[i].id=i;
    }
    sort(ask+1,ask+1+m,cmp_1);
    for(int i=1,l=1,r=0;i<=m;i++){
        for(;r<ask[i].r;r++) update(r+1,1);
        for(;r>ask[i].r;r--) update(r,-1);
        for(;l<ask[i].l;l++) update(l,-1);
        for(;l>ask[i].l;l--) update(l-1,1);
        if(ask[i].l==ask[i].r){
            ask[i].a=0,ask[i].b=1;continue;
        }
        ask[i].a=ans-(ask[i].r-ask[i].l+1);
        ask[i].b=(ll)(ask[i].r-ask[i].l+1)*(ask[i].r-ask[i].l);
        ll k=__gcd(ask[i].a,ask[i].b);
        ask[i].a/=k,ask[i].b/=k;
    }
    sort(ask+1,ask+m+1,cmp_2);
    for(int i=1;i<=m;i++)
        printf("%lld/%lld\n",ask[i].a,ask[i].b);
    //system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注