http://www.codeforces.com/contest/703/problem/D D. Mishka and Interesting sum （莫队的TLE）

66 阅读 0 评论 44 点赞

我是靠谱客的博主粗心项链，最近开发中收集的这篇文章主要介绍http://www.codeforces.com/contest/703/problem/D D. Mishka and Interesting sum （莫队的TLE），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*
莫队算法的常数优化 实战演练 虽然是TLE代码
*/

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000000 + 100;
int block;
struct query{
    int l, r, id;
    bool operator < (const query &rhs)const{
        return (l/block == rhs.l /block) ? r < rhs.r : l/block < rhs.l/block;
    }
}q[maxn];

int a[maxn];
int cnt[maxn];
int ans[maxn];
int pre[maxn];

int main(){
    int n;
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    pre[0] = 0;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), pre[i] = pre[i-1]^a[i];
    int m;
    scanf("%d", &m);
    block = ceil(sqrt(m*1.0));
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i + 1;
    }
    sort(q, q + m);
    int curl, curr;
    curl = curr = 0;
    int res = 0;
    for(int i = 0; i < m; ++i){
        if(i){
            if(q[i].r < q[i-1].r){
                while(curl <= curr) cnt[a[curl++]] = 0;
                res = 0;
                curl = q[i].l;
                curr = q[i].r;
                //++cnt[a[curl]];
                int k = curl;
                while(k <= curr){
                    ++cnt[a[k]];
                    if(cnt[a[k]] == 1) res ^= a[k];
                    ++k;
                }
                ans[q[i].id] = res^pre[q[i].r]^pre[q[i].l-1];
                continue;
            }
        }

        if(curl < q[i].l){
            while(curl < q[i].l){
                --cnt[a[curl]];
                if(cnt[a[curl]] == 0)
                    res ^= a[curl];
                ++curl;
            }
        }
        if(curl > q[i].l){
            while(curl > q[i].l){
                --curl;
                ++cnt[a[curl]];
                if(cnt[a[curl]] == 1)
                     res ^= a[curl];
            }
        }
        if(curr < q[i].r){
            while(curr < q[i].r){
                ++curr;
                ++cnt[a[curr]];
                 if(cnt[a[curr]] == 1)
                    res ^= a[curr];
            }
        }
        if(curr > q[i].r){
            while(curr > q[i].r){
                --cnt[a[curr]];
               if(cnt[a[curr]] == 0)
                    res ^= a[curr];
                --curr;
            }
        }
        ans[q[i].id] = res^pre[q[i].r]^pre[q[i].l-1];
    }
    for(int i = 1; i <= m; ++i) printf("%dn", ans[i]);
}