https://www.lydsy.com/JudgeOnline/problem.php?id=2038

題解：分塊+莫隊算法

參考文章：https://blog.csdn.net/weixin_43272781/article/details/86582353

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=50000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; ll ans,cnt,flag,temp,num; int a[N]; int pos[N]; int f[N]; char str; ll gcd(ll a,ll b){if(a<b)swap(a,b);while(b){int r=a%b;a=b;b=r;}return a; } struct node{int l,r,id;ll a,b;void mod(){ll tmp=gcd(a,b);a/=tmp;b/=tmp;}bool operator <(const node &S)const{if(pos[l]==pos[S.l])return pos[r]<pos[S.r];return pos[l]<pos[S.l];}}e[N]; bool cmp(const node a,const node b){return a.id<b.id; } void modify(int p,int add){ans=ans+2*add*f[a[p]]+1;f[a[p]]+=add; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d%d",&n,&m);//scanf("%d",&t);//while(t--){}q=sqrt(n);for(int i=1;i<=n;i++)pos[i]=(i-1)/q+1;for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=m;++i){scanf("%d%d",&e[i].l,&e[i].r);e[i].id=i;}sort(e+1,e+m+1);int l=1,r=0;for(int i=1;i<=m;++i){if(r<e[i].r){while(++r<e[i].r)modify(r,1);modify(r,1);}if(l>e[i].l){while(--l>e[i].l)modify(l,1);modify(l,1);}if(e[i].r<r){modify(r,-1);while(e[i].r<--r)modify(r,-1);}if(l<e[i].l){modify(l,-1);while(++l<e[i].l)modify(l,-1);}if(e[i].l==e[i].r){e[i].a=0;e[i].b=1;continue;}e[i].a=ans-(e[i].r-e[i].l+1),e[i].b=(ll)(e[i].r-e[i].l+1)*(e[i].r-e[i].l);e[i].mod();}sort(e+1,e+m+1,cmp);for(int i=1;i<=m;++i)printf("%lld/%lld\n",e[i].a,e[i].b);//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的小Z的袜子(hose)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。