A simple Blog for wyx I've been down the bottle hoping.
2038: [2009国家集训队]小Z的袜子(hose) 莫队
发表于: | 分类: Oi | 评论:0 | 阅读:146

莫队裸题

暴力怎么做?选定左端点然后一点一点向右扩展就行了,从[l,r]到[l,r+1]只需要考虑这个颜色对答案的影响

按照左端点所在块为第一关键字,右端点为第二关键字将询问离线排序

然后我们来进行一波大暴力就能过辣!

以下是复杂度证明

1,当左端点固定在一个块内的时候,由于右端点单调所有右端点移动复杂度为$O(n)$,而左端点只可能在$\sqrt{n}$块内

2,当左端点在块内移动的时候,每次最多移动$\sqrt{n}$,然后最多移动$\sum{Q}$次。

3,换块的时候,右端点最多挪$n$,最多换$\sqrt{n}$次

然后就是令人愉悦的暴力了

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4+5;
LL sum[N], ans, l, r; int col[N], n, m, sz, i;
struct data { int id,blo, l, r;LL a, b; } a[N];
inline bool cmp2(const data &a,const data &b) { return a.id < b.id; }
inline bool cmp1(const data &a,const data &b) { return a.blo != b.blo ? a.blo < b.blo : a.r < b.r; }
inline void updata(int x,int val) { ans -= sum[col[x]] * sum[col[x]]; sum[col[x]] += val; ans += sum[col[x]] * sum[col[x]]; }
inline int read() {int x=0,f=1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}return x*f;}
int main() {
    n = read(), m = read(), sz = (int)sqrt(n);
    for(i=1;i<=n;++i) col[i] = read();
    for(i=1;i<=m;++i) a[i].l = read(), a[i].r = read(), a[i].blo = a[i].l / sz, a[i].id = i;
    sort(a+1,a+m+1,cmp1);
    for(l=1,r=0,i=1;i<=m;++i) {
        while(a[i].r < r) updata(r--,-1);   while(a[i].r > r) updata(++r,+1); 
        while(a[i].l < l) updata(--l,+1);   while(a[i].l > l) updata(l++,-1);
        a[i].a = ans-(r-l+1), a[i].b = (r-l+1)*(r-l);
    } sort(a+1,a+m+1,cmp2);
    for(i=1;i<=m;++i) printf("%lld/%lld\n",a[i].a/__gcd(a[i].a,a[i].b),a[i].b/__gcd(a[i].a,a[i].b));
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP