bzoj 2038 莫队
发布日期:2021-08-17 08:27:56 浏览次数:0 分类:技术文章

题意:中文题

思路:经典的,莫队算法了。

对于L,R的询问。设其中颜色为x,y,z....的袜子的个数为a,b,c。。。那么答案即为(a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2)化简得:(a^2+b^2+c^2+...x^2-(a+b+c+d+.....))/((R-L+1)*(R-L))

上面组合数的化简来自 (我没化出来。。。TOT)

所以就只要统计区间内每个数出现的次数就可以了

复杂度的问题。

在所有询问中,R是单调递增的,也就是R在整个离线求解过程中只会跑一遍,L在最坏的情况下是在一个块内来回跑,因为有sqrt(n)块,每块的长度是sqrt(n),所以L最坏的情况下是nsqrt(n)

AC代码:

#include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define ll long long#define endl ("\n")#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;#define mem(a,x) memset(a,x,sizeof(a))#define mp(x,y) make_pair(x,y)#define pb(x) push_back(x)#define ft first#define sd second#define lrt (rt<<1)#define rrt (rt<<1|1)using namespace std;const ll INF = 1e18+1LL;const int inf = 1e9+1e8;const int N=1e5+100;const ll mod=1e9+7;int n,m,unit,a[N];ll num[N],temp;struct Cap_Mo{    struct Qu{        int l, r, id;        bool friend operator< (Qu a, Qu b){            if(a.l/unit != b.l/unit) return a.l<b.l;            return a.r<b.r;        }    }q[N];    struct Ans{        ll a, b;        void reduce(){            ll d=__gcd(a,b);            a/=d, b/=d;        }    }ans[N];    void add(int x){        temp -= num[a[x]]*num[a[x]];        num[a[x]]++;        temp += num[a[x]]*num[a[x]];    }    void del(int x){        temp -= num[a[x]]*num[a[x]];        num[a[x]]--;        temp += num[a[x]]*num[a[x]];    }    void work(){        ll L=1, R=0;        for(int i=1; i<=m; ++i){            while(R < q[i].r){                add(++R);            }            while(R > q[i].r){                del(R--);            }            while(L > q[i].l){                add(--L);            }            while(L < q[i].l){                del(L++);            }            ans[q[i].id].a=temp - (R-L+1);            ans[q[i].id].b=(R-L+1)*(R-L);            ans[q[i].id].reduce();        }    }}Mo;int main(){    scanf("%d %d", &n,&m);    for(int i=1; i<=n; ++i){        scanf("%d",&a[i]);    }    for(int i=1; i<=m; ++i){        scanf("%d %d",&Mo.q[i].l,&Mo.q[i].r);        Mo.q[i].id=i;    }    unit=(int)sqrt(n);    sort(Mo.q+1, Mo.q+1+m);    Mo.work();    for(int i=1; i<=m; ++i){        printf("%lld/%lld\n",Mo.ans[i].a, Mo.ans[i].b);    }    return 0;}

 

转载于:https://www.cnblogs.com/max88888888/p/7346337.html

上一篇:11、java常用单词(转载)
下一篇:习题二(7)