小Z的袜子(hose)

 莫队经典

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define LL long long  7 using namespace std; 8 const int maxn = 50010; 9 LL gcd(LL a, LL b){10     return b == 0 ? a : gcd(b, a % b);11 }12 struct Qry{13     LL l, r, pos, id;14     LL a, b;15     bool operator < (const Qry &a)const{16         if(pos == a.pos) return r < a.r;17         return l < a.l;18     }19 }q[maxn];20 LL c[maxn], s[maxn];21 LL ans;22 void update(LL p, LL v){23     ans += 2 * v * s[c[p]] + 1;24     s[c[p]] += v;25 }26 bool cmp(Qry x, Qry y){27     return x.id < y.id;28 }29 void solve(LL n, LL m){30     LL l = 1, r = 0;31     ans = 0;32     for(LL i = 0; i < m; i++){33         while(l < q[i].l) update(l++, -1);34         while(l > q[i].l) update(--l, 1);35         while(r > q[i].r) update(r--, -1);36         while(r < q[i].r) update(++r, 1);37         if(q[i].l == q[i].r) {q[i].a = 0; q[i].b = 1; continue;}38         q[i].a = ans - (q[i]. r - q[i]. l + 1);39         q[i].b = (q[i]. r - q[i]. l + 1) * (q[i].r - q[i].l);40         LL g = gcd(q[i].a, q[i].b);41         q[i].a /= g; q[i].b /= g;42     }43     sort(q, q + m, cmp);44 }45 46 int main(){47     LL n, m;48     while(scanf("%lld %lld", &n, &m) != EOF){49         memset(s, 0, sizeof s);50         for(LL i = 1; i <= n; i++){51             scanf("%lld", &c[i]);52         }53         LL SZ = sqrt(n * 1.0);54         for(LL i = 0; i < m; i++){55             scanf("%lld %lld", &q[i].l, &q[i].r);56             q[i].id = i;57             q[i].pos = (q[i].l - 1) / SZ + 1;58         }59         sort(q, q + m);60         solve(n, m);61         for(LL i = 0; i < m; i++) printf("%lld/%lld\n", q[i].a, q[i].b);62     }63 }