问题:解决 q
q q次询问,每次询问 [
L
,
R
]
[L,R] [L,R]中有多少对 (
i
,
j
)
,
满足
a
i
=
=
a
j
(i,j),满足a_i==a_j (i,j),满足ai==aj
先想点超时但是可以解决的方法:
对于每次询问,枚举 L
<
=
i
<
=
R
L<=i<=R L<=i<=R中的元素,令 n
u
m
[
i
]
num[i] num[i]为 i
i i元素出现的次数,显然这样的对数是 n
u
m
[
i
]
∗
(
n
u
m
[
i
]
−
1
)
/
2
num[i]*(num[i]-1)/2 num[i]∗(num[i]−1)/2
注意下题目似乎是静态的,并不是动态的。也许可以利用这点.
然而并没有想出来,据说是一种叫莫队的算法。
学习完莫队,发现这是莫队的板子题,真是富有启发性。
利用查询区间之间的信息,进行信息合并,很美妙的一个算法.
/*
Tonight I wanna drown in an ocean of you
*/ #include using namespace std; const int INF = 1e9+7; const int maxn = 1e6+5; typedef long long ll; typedef pair<int,int> pii; #define all(a) (a).begin(), (a).end() #define pb(a) push_back(a) vector<int> G[maxn]; int mx; struct Node{ int l,r,id; bool operator < (const Node &rhs)const{ if(l/mx!=rhs.l/mx) return l<rhs.l; if((l/mx)&1) return r < rhs.r; return r>rhs.r; } };//询问序列 Node q[maxn]; ll sum = 0;int cnt[maxn];int a[maxn]; void add(int i){ sum += cnt[i]; cnt[i]++; } void del(int i){ cnt[i]--; sum -= cnt[i]; } ll gcd(ll a,ll b){ if(!b) return a; return gcd(b,a%b); } ll ans1[maxn],ans2[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; mx = n / sqrt(n*2/3); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<m;i++) cin>>q[i].l>>q[i].r,q[i].id = i; sort(q,q+m); for(int i=0,l=1,r=0;i<m;i++){ if(q[i].l==q[i].r){ ans1[q[i].id] = 0,ans2[q[i].id] = 1; continue; } while(l>q[i].l) add(a[--l]); while(r<q[i].r) add(a[++r]); while(l<q[i].l) del(a[l++]); while(r>q[i].r) del(a[r--]); ans1[q[i].id] = sum; //分子 ans2[q[i].id] = 1LL*(r-l+1)*(r-l)/2; //分母 } for(int i=0;i<m;i++){ if(ans1[i]!=0){ ll g = gcd(ans1[i],ans2[i]); ans1[i]/=g,ans2[i]/=g; } else ans2[i] = 1; cout<<ans1[i]<<"/"<<ans2[i]<<"\n"; } }
