杂题专练(二)

BZOJ 2527

题目大意:自己看..

解题报告

JeremyGuo欺骗我…她说这道题复杂度可以有[latex]O(N\times log_2(N))[/latex]想了好久发现是假的..
首先这题当然可以用可持久化线段树之类来做, 但是CDQ+树状数组明显更好写。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 300030;
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int N, M, K;
int O[MAXN], P[MAXN];
int oper[MAXN][3];
LL C[MAXN];
inline int lowbit (int a) {return a&-a;}
inline void add (int p, int v) {
    while(p <= M) C[p] += v, p += lowbit(p);
}
inline LL query (int p) {
    LL ret = 0;
    while(p) ret += C[p], p -= lowbit(p);
    return ret;
}
int ans[MAXN];
vector<int> pos[MAXN];
inline void runOper (int i, int t) {
    if(oper[i][0] <= oper[i][1])
        add(oper[i][0], t*oper[i][2]), add(oper[i][1]+1, -t*oper[i][2]);
    else {
        add(1, t*oper[i][2]), add(oper[i][1]+1, -t*oper[i][2]);
        add(oper[i][0], t*oper[i][2]);
    }
}
void solve (vector<int> & vec, int l, int r) {
    if(l == r) {
        runOper(l, 1);
        for(int i = 0; i<(int)vec.size(); i++)
            ans[vec[i]] = l;
        return ;
    }
    int mid = (l+r)>>1;
    for(int i = l; i<=mid; i++)
        runOper(i, 1);
    vector<int> lef, rig;
    for(int p = 0; p<(int)vec.size(); p++) {
        LL sum = 0;
        for(int i = 0; i<(int)pos[vec[p]].size(); i++) {
            sum += query(pos[vec[p]][i]);
            if(sum >= P[vec[p]]) break;
        }
        if(sum >= P[vec[p]]) lef.push_back(vec[p]);
        else rig.push_back(vec[p]);
    }
    for(int i = l; i<=mid; i++)
        runOper(i, -1);
    solve(lef, l, mid);
    solve(rig, mid+1, r);
}
vector<int> vec;
int main () {
    N = getInt(), M = getInt();
    for(int i = 1; i<=M; i++)
        pos[O[i] = getInt()].push_back(i);
    for(int i = 1; i<=N; i++) P[i] = getInt();
    K = getInt();
    for(int i = 1; i<=K; i++)
        oper[i][0] = getInt(), oper[i][1] = getInt(), oper[i][2] = getInt();
    oper[K+1][0] = oper[K+1][1] = oper[K+1][2] = 1;
    for(int i = 1; i<=N; i++) vec.push_back(i);
    solve(vec, 1, K+1);
    for(int i = 1; i<=N; i++)
        if(ans[i] > K) puts("NIE");
        else printf("%d\n", ans[i]);
}

BZOJ 4103

题目大意:给你数组A和B, p个询问, 每次询问可重集合[latex]S={A_i \, xor \, B_j \mid u\le i\le d, l\le j \le r}[/latex]中第k大的元素。

解题报告

一开始直接偷懒暴力, 写完暴力发现是错的, 自己zz了。
然后发现在PST(或者说可持久化Trie, 其实也算是PST的变种吧)上暴力就好了, 只是复杂度略有点玄。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXM = 300030;
const int MAXN = 1010;
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int N, M;
namespace PST {
    const int MAXD = MAXM*32;
    struct Node {
        int ch[2];
        int sz;
    } d[MAXD];
    int dtot = 0;
    int roots[MAXM], tot;
    unsigned ins;
    void insert (int & u, int r, int b, bool l) {
        if(l != (bool)(ins&(1u<<b))) {u = r; return ;}
        d[u = ++dtot].sz = d[r].sz+1;
        if(!b) return ;
        insert(d[u].ch[0], d[r].ch[0], b-1, false);
        insert(d[u].ch[1], d[r].ch[1], b-1, true);
    }
    inline void hInsert (unsigned val) {
        ins = val, ++tot;
        insert(roots[tot], roots[tot-1], 31, false);
    }
    inline int size (int u) {return d[u].sz;}
}
int A[MAXN], B[MAXM];
int bufl[MAXN], bufr[MAXN];
int main () {
    N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++) A[i] = getInt();
    for(int i = 1; i<=M; i++) {
        B[i] = getInt();
        PST::hInsert(B[i]);
    }
    int P = getInt();
    for(int q = 1; q<=P; q++) {
        int x1 = getInt(), x2 = getInt();
        int y1 = getInt(), y2 = getInt(), k = getInt();
        int cur = 0;
        for(int i = x1; i<=x2; i++) {
            bufl[i-x1+1] = PST::roots[y1-1];
            bufr[i-x1+1] = PST::roots[y2];
        }
        int xlen = x2-x1+1;
        for(int p = 30; p>=0; p--) {
            int cnt1 = 0;
            for(int i = 1; i<=xlen; i++) {
                if(A[i+x1-1]&(1<<p))
                    cnt1 += PST::size(PST::d[bufr[i]].ch[0])-PST::size(PST::d[bufl[i]].ch[0]);
                else cnt1 += PST::size(PST::d[bufr[i]].ch[1])-PST::size(PST::d[bufl[i]].ch[1]);
            }
            bool flg = true;
            if(cnt1 < k) k -= cnt1, flg = false;
            else cur |= (1<<p);
            for(int i = 1; i<=xlen; i++) {
                bufl[i] = PST::d[bufl[i]].ch[flg^(bool)(A[i+x1-1]&(1<<p))];
                bufr[i] = PST::d[bufr[i]].ch[flg^(bool)(A[i+x1-1]&(1<<p))];
            }
        }
        printf("%d\n", cur);
    }
}

BZOJ 3489

题目大意:给个序列A, 每次询问一个区间[l, r]内最大的只出现一次的数字。

解题报告

…没想出来, 我果然zz。
首先考虑每个数字会对哪一段区间做出贡献, 对于数字A[i], 设A[i]上一次出现位置为pre[i], 下一次出现位置为suc[i], 那么i可以对所有区间[l, r]满足pre[i]<l≤i并且pre[i]≤r<suc[i]做出贡献, 把区间l和r看成坐标系上的点, 每个贡献就是一个矩形, 用树套树做矩形取max和单点查询操作即可。
这种考虑贡献的思路还是比较好的…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
const int MAXN = 200020;
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int N, M;
namespace PST {
    const int MAXD = MAXN*100;
    int lc[MAXD], rc[MAXD], mxv[MAXD]; // 下标元素01和线段树
    int dtot, insl, insr, insv;
    void insert (int & u, int l, int r) {
        if(l > insr || r < insl) return ;
        if(!u) u = ++dtot;
        if(insl <= l && r <= insr) {mxv[u] = max(insv, mxv[u]); return ;}
        int mid = (l+r)>>1;
        insert(lc[u], l, mid), insert(rc[u], mid+1, r);
    }
    int qp;
    int query (int u, int l, int r) {
        if(!u || l > qp || r < qp) return 0;
        if(l == r) return mxv[u];
        int mid = (l+r)>>1;
        return max(mxv[u], max(query(lc[u], l, mid), query(rc[u], mid+1, r)));
    }
    int uid[MAXN*4];
    int insyl, insyr;
    void insertY (int u, int l, int r) {
        if(l > insyr || r < insyl) return ;
        if(insyl <= l && r <= insyr) {insert(uid[u], 1, N); return ;}
        int mid = (l+r)>>1;
        insertY(u<<1, l, mid);
        insertY((u<<1)+1, mid+1, r);
    }
    void handleInsert (int x1, int x2, int y1, int y2, int val) {
        insl = x1, insr = x2, insyl = y1, insyr = y2;
        insv = val;
        insertY(1, 1, N);
    }
    int qyp;
    int queryY (int u, int l, int r) {
        if(l > qyp || r < qyp) return 0;
        int val = query(uid[u], 1, N);
        if(l == r) return val;
        int mid = (l+r)>>1;
        return max(val, max(queryY(u<<1, l, mid), queryY((u<<1)+1, mid+1, r)));
    }
    int handleQuery (int invl, int invr) {
        qp = invl, qyp = invr;
        return queryY(1, 1, N);
    }
}
int A[MAXN], pre[MAXN], suc[MAXN], cur[MAXN];
int main () {
    N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++) {
        A[i] = getInt();
        pre[i] = cur[A[i]];
        cur[A[i]] = i;
    }
    for(int i = 1; i<=N; i++) cur[i] = N+1;
    for(int i = N; i>=1; i--) {
        suc[i] = cur[A[i]];
        cur[A[i]] = i;
    }
    for(int i = 1; i<=N; i++)
        PST::handleInsert(pre[i]+1, i, i, suc[i]-1, A[i]);
    int lastans = 0;
    for(int i = 1; i<=M; i++) {
        int x = getInt(), y = getInt();
        int l = min((x+lastans)%N+1, (y+lastans)%N+1);
        int r = max((x+lastans)%N+1, (y+lastans)%N+1);
        printf("%d\n", lastans=PST::handleQuery(l, r));
    }
}

BZOJ 3545/3551

题目大意:给你一个图, 点边都带权, 每次询问一个点经过不超过x边权的边能到达的所有点中点权第k大的。
强制在线。

解题报告

Kruskal重构树!学了跟没学一样!想不到!
首先做一颗Kruskal重构树出来, 然后问题就转化成静态在线子树第k大了, 用dfn+主席树上整体二分解决。

代码

这里贴未进行强制在线解码的版本。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100050;
const int MAXM = 500050;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '0');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int len;
namespace PST {
    const int MAXD = MAXN*35;
    int lc[MAXD], rc[MAXD], sum[MAXD], dtot;
    int roots[MAXN*2], tot;
    int insp, insv;
    void insert (int & u, int lb, int rb, int r) {
        if(lb > insp || rb < insp) {u = r; return ;}
        if(!u) u = ++dtot, sum[u] = sum[r];
        sum[u] += insv;
        if(lb == rb) return ;
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
    }
    void handleInsert (int val, int cnt) {
        ++tot, insp = val, insv = cnt;
        insert(roots[tot], 1, len, roots[tot-1]);
    }
    int queryKth (int l, int r, int k) {
        int x = roots[l-1], y = roots[r];
        int lb = 1, rb = len;
        while(lb != rb) {
            int csum = sum[rc[y]]-sum[rc[x]];
            int mid = (lb+rb)>>1;
            if(csum < k) k -= csum, x = lc[x], y = lc[y], rb = mid;
            else x = rc[x], y = rc[y], lb = mid+1;
        }
        if(k > sum[y]-sum[x]) return 0; // no solution
        return lb;
    }
}
struct Edge {
    int a, b, w;
} edges[MAXM];
inline bool operator < (const Edge & a, const Edge & b) {
    return a.w < b.w;
}
int N, M, Q;
int pfa[MAXN*2];
int root (int u) {return pfa[u]?(pfa[u]=root(pfa[u])):u;}
int dtot;
struct Node {
    int v, nxt;
} d[MAXN*3];
int head[MAXN*2], etot;
inline void addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
}
int dfn[MAXN*2], lst[MAXN*2], rev[MAXN*2], dfntot;
int H[MAXN*2], hlinr[MAXN*2], fa[MAXN*2][20];
void dfs (int u, int f) {
    fa[u][0] = f;
    rev[dfn[u] = ++dfntot] = u;
    for(int e = head[u]; e; e = d[e].nxt)
        dfs(d[e].v, u);
    lst[u] = dfntot;
}
int maxv[MAXN*2][20];
void stSetup () {
    maxv[0][0] = INF;
    for(int i = 1; i<=dfntot; i++)
        maxv[i][0] = max(maxv[i][0], maxv[fa[i][0]][0]);
    for(int lvl = 1; lvl<20; lvl++)
        for(int i = 1; i<=dfntot; i++) {
            maxv[i][lvl] = max(maxv[fa[i][lvl-1]][lvl-1], maxv[i][lvl-1]);
            fa[i][lvl] = fa[fa[i][lvl-1]][lvl-1];
        }
}
int stQuery (int u, int lim) {
    for(int i = 19; i>=0; i--)
        if(maxv[u][i] <= lim) u = fa[u][i];
    return u;
}
int roots[MAXN*2], rtot;
int main () {
    N = getInt(), M = getInt(), Q = getInt();
    for(int i = 1; i<=N; i++) H[i] = getInt();
    for(int i = 1; i<=M; i++) {
        edges[i].a = getInt();
        edges[i].b = getInt();
        edges[i].w = getInt();
    }
    dtot = N;
    std :: sort(edges+1, edges+M+1);
    for(int i = 1; i<=M; i++) {
        int ra = root(edges[i].a), rb = root(edges[i].b);
        if(ra == rb) continue ;
        int u = ++dtot;
        pfa[ra] = u, pfa[rb] = u;
        maxv[u][0] = edges[i].w;
        addEdge(u, ra), addEdge(u, rb);
    }
    for(int i = 1; i<=dtot; i++)
        if(root(i) == i) roots[++rtot] = i;
    for(int i = 1; i<=rtot; i++)
        dfs(roots[i], 0);
    stSetup();
    memcpy(hlinr, H, sizeof H);
    sort(hlinr+1, hlinr+N+1);
    len = (unique(hlinr+1, hlinr+N+1)-hlinr)-1;
    for(int i = 1; i<=dfntot; i++) {
        int val = lower_bound(hlinr, hlinr+len+1, H[rev[i]])-hlinr;
        PST::handleInsert(val, rev[i]<=N);
    }
    hlinr[0] = -1;
    for(int q = 1; q<=Q; q++) {
        int u = getInt(), x = getInt(), k = getInt();
        int pos = stQuery(u, x);
        printf("%d\n", hlinr[PST::queryKth(dfn[pos], lst[pos], k)]);
    }
}

BZOJ 3439

题目大意: 给你N个串, 对每个串询问一次出现过的以这个串结尾的串中编号第k小的串编号。

解题报告

《论哈希之美与STLの胜利》

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 100010;
const int MAXL = 300030;
const ULL SEED = 31;
int N;
char buf[MAXL];
ULL rec[MAXN];
map<ULL, priority_queue<int> > mp;
map<ULL, priority_queue<pair<int, int> > > mp2;
int ans[MAXN], K[MAXN];
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        int len;
        reverse(buf, buf+(len=strlen(buf)));
        ULL hashc = 0;
        for(int j = 0; j<len; j++) {
            hashc = hashc*SEED+buf[j];
            mp[hashc].push(i);
        }
        rec[i] = hashc;
    }
    for(int i = 1; i<=N; i++)
        scanf("%d", &K[i]), mp2[rec[i]].push(make_pair(K[i], i));
    for(map<ULL, priority_queue<pair<int, int> > >::iterator it = mp2.begin(); it != mp2.end(); it++) {
        priority_queue<pair<int, int> > &que = it->second;
        while(!que.empty()) {
            pair<int, int> qry = que.top();
            que.pop();
            priority_queue<int>&st = mp[it->first];
            while(st.size() > qry.first) st.pop();
            if(st.size() < qry.first) ans[qry.second] = -1;
            else ans[qry.second] = st.top();
        }
    }
    for(int i = 1; i<=N; i++)
        printf("%d\n", ans[i]);
}

BZOJ 4105

题目大意: 给你一个数列A和数字P(P在数据范围中给出), 支持两种操作:
1.区间A[i]变成A[i]*A[i]%P。
2.区间求和。

解题报告

鬼畜题..可以发现对于每一个给定的P模数, 有一个神奇的性质。如果把x向x*x%P连边, 那么图上最大的环长度很小, 并且所有环长度的lcm最大为60, 并且每一个节点到环的距离不超过11。
然后就可以用线段树做, 每个节点保存如果这个区间进行操作1若干次(小于环lcm次)之后的区间和, 不在环上的stl暴力就可以了..
自己zz感觉不用写updata调了半个小时…rool(操作1)是需要updata的。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
const int MAXN = 100010;
int N, M, P;

int vis[MAXN];
bool cvis[MAXN];
int cid[MAXN], clen[MAXN], ctot;
bool dfs (int u, int d) {
    if(vis[u]) {
        if(cvis[u]) {clen[cid[u] = ++ctot] = d-vis[u]; return true;}
        return false;
    }
    vis[u] = d; cvis[u] = true;
    if(dfs(u*u%P, d+1)) {
        cvis[u] = false;
        if(cid[u] == ctot) return false;
        cid[u] = ctot; return true;
    }
    cvis[u] = false;
    return false;
}
int cirlcm; // 记住初始化!
namespace IBT {
    const int MAXD = MAXN*5;
    const int BLEN = 80;
    int val[MAXD][BLEN]; // u节点经过i次操作的和/当前和
    int rcnt[MAXD]; // 保存旋转次数
    int buf[BLEN];
    inline void rool (int u, int t) {
        rcnt[u] += t;
        memcpy(buf, val[u], sizeof buf);
        for(int i = 0; i<cirlcm; i++)
            val[u][i] = buf[(i+t)%cirlcm];
    }
    inline void updata (int u) {
        for(int i = 0; i<cirlcm; i++)
            val[u][i] = val[u<<1][i]+val[(u<<1)+1][i];
    }
    inline void pushdown (int u) {
        if(rcnt[u]) {
            rool(u<<1, rcnt[u]);
            rool((u<<1)+1, rcnt[u]);
            rcnt[u] = 0;
        }
    }
    int insp, insv[BLEN], inslen;
    inline void mixin (int u) {
        for(int i = 0; i<cirlcm; i++)
            val[u][i] += insv[i%inslen];
    }
    void insert (int u, int l, int r) {
        if(l > insp || r < insp) return ;
        mixin(u);
        if(l == r) return ;
        pushdown(u);
        int mid = (l+r)>>1;
        insert(u<<1, l, mid);
        insert((u<<1)+1, mid+1, r);
    }
    int argl, argr;
    void rooldown (int u, int l, int r) {
        if(l > argr || r < argl) return ;
        if(argl <= l && r <= argr) {rool(u, 1); return ;}
        pushdown(u);
        int mid = (l+r)>>1;
        rooldown(u<<1, l, mid);
        rooldown((u<<1)+1, mid+1, r);
        updata(u);
    }
    int query (int u, int l, int r) {
        if(l > argr || r < argl) return 0;
        if(argl <= l && r <= argr) return val[u][0];
        pushdown(u);
        int mid = (l+r)>>1;
        return query(u<<1, l, mid)+query((u<<1)+1, mid+1, r);
    }
}
int A[MAXN];
void handleInsert (int pos, int num) {
    num %= P;
    int t = num*num%P, p = 0;
    IBT::insv[0] = num;
    while(t != num) {
        IBT::insv[++p] = t;
        t = t*t%P;
    }
    IBT::inslen = p+1;
    IBT::insp = pos;
    IBT::insert(1, 1, N);
}
set<int> st;
inline void handleRool (int l, int r) {
    IBT::argl = l, IBT::argr = r;
    set<int>::iterator it = st.lower_bound(l), tmp;
    IBT::rooldown(1, 1, N);
    while(it != st.end() && *it <= r) {
        int p = *it;
        A[p] = A[p]*A[p]%P;
        tmp = it, ++ it;
        if(cid[A[p]]) {
            st.erase(tmp);
            handleInsert(p, A[p]);
        }
    }
}
inline int handleQuery (int l, int r) {
    IBT::argl = l, IBT::argr = r;
    set<int>::iterator it = st.lower_bound(l);
    int sum = 0;
    while(it != st.end() && *it <= r)
        sum += A[*it], ++ it;
    return sum+IBT::query(1, 1, N);
}
int gcd (int a, int b) {return b ? gcd(b, a%b) : a;}
inline int lcm (int a, int b) {return a/gcd(a, b)*b;}
int main () {
    scanf("%d%d%d", &N, &M, &P);
    cirlcm = 1;
    for(int i = 0; i<P; i++)
        if(!vis[i]) dfs(i, 1);
    for(int i = 1; i<=ctot; i++) cirlcm = lcm(cirlcm, clen[i]);
    for(int i = 1; i<=N; i++) {
        scanf("%d", &A[i]), A[i] %= P;
        if(cid[A[i]]) handleInsert(i, A[i]);
        else st.insert(i);
    }
    for(int i = 1; i<=M; i++) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 0) handleRool(l, r);
        else printf("%d\n", handleQuery(l, r));
    }
}
/*
6 100 11
1 7 10 4 10 4
0 2 4
1 4 5
15!
1 3 4
1 1 5
0 3 5
1 1 3
*/

BZOJ 3744

题目大意: 给你一个串, 强制在线区间逆序对。

解题报告

%#$^%@!
分块+主席树乱搞!
真的那么简单么?
交上去, Time Limit Exceed!
生成大数据! 擀! 要跑18s!
怎么可能QAQ
Hineven: Ender我好像被常数附体了你的代码借我跑一下。
Ender: 好的。
Ender的代码只跑了3s+!
Hineven:%#$^%@!你怎么写的?!
Ender:树状数组加预处理啊。
Hineven:%#$^%@!
Hineven差点就转行写树状数组了!
JeremyGuo:我写的主席树没问题啊。
JermeyGuo跑了多久呢? 4s!
Hineven:[****哔****!]
JeremyGuo:我来帮你优化一下。
[30min之后…]
JeremyGuo:优化完了!PST每处理4k个询问查询次数下降了一半呢!
现在优化到13s了1
JeremyGuo:加油我先走了。
Hineven:你多少分一块?
JeremyGuo:128?
Hineven:$$%#$$$#@$!#!
然后Hineven就把块内元素从256个改到128个!现在只需要9s了!
Hineven:用暴力复杂度换PST果然正解!
然后开1k个块, 5s!交!过了!
4h啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 50050;
int len;
namespace PST {
    const int MAXD = MAXN*20;
    int lc[MAXD], rc[MAXD], sum[MAXD], dtot;
    int roots[MAXN], tot;
    int insp;
    /*void insert (int& u, int l, int r, int v) {
        if(l > insp || r < insp) {u = v; return ;}
        if(!u) u = ++dtot, sum[u] = sum[v];
        sum[u] ++;
        if(l == r) return ;
        int mid = (l+r)>>1;
        insert(lc[u], l, mid, lc[v]);
        insert(rc[u], mid+1, r, rc[v]);
    }*/
    void Insert(int& u, int l, int r, int pos){
        ++dtot;
        lc[dtot] = lc[u];
        rc[dtot] = rc[u];
        sum[dtot] = sum[u]+1;
        u = dtot;
        if(l == r) return ;
        int mid=(l+r)>>1;
        if(pos <= mid) Insert(lc[u], l, mid, pos);
        else Insert(rc[u], mid+1, r, pos);
    }
    inline void handleInsert (int val) {
        insp = val, tot ++;
        //insert(roots[tot], 1, len, roots[tot-1]);
        roots[tot] = roots[tot-1];
        Insert(roots[tot], 1, len, val);
    }
    int ql, qr;
    int query (int u, int u2, int l, int r) {
        if(u2 == u) return 0;
        if(ql <= l && r <= qr) return sum[u]-sum[u2];
        int mid = (l+r)>>1;
        int ret=0;
        if(ql <= mid) ret += query(lc[u], lc[u2], l, mid);
        if(qr > mid) ret += query(rc[u], rc[u2], mid+1, r);
        return ret;
    }
    /*int Query(int lrt, int rrt, int l, int r, int L, int R){
        if(L <= l && r <= R)
            return sum[rrt]-sum[lrt];
        d_sum++;
        int mid=(l+r)>>1;
        int ret=0;
        if(L <= mid)
            ret += Query(lc[lrt], lc[rrt], l, mid, L, R);
        if(R > mid)
            ret += Query(rc[lrt], rc[rrt], mid+1, r, L, R);
        return ret;
    }*/
    inline int handleQuery (int x1, int x2, int y1, int y2) {
        if(x1 > x2 || y1 > y2) return 0;
        x1 --, ql = y1, qr = y2;
        return query(roots[x2], roots[x1], 1, len);
        //return Query(roots[x1], roots[x2], 1, len, y1, y2);
    }
}
int N, qsize, qtot;
int A[MAXN];
const int QCNT = 1000;
vector<int> quads[1000];
int qconflict[1000];
int cconflict[1000][1000];
int cvalue[1000][1000];
int linr[MAXN];
inline int getConflict (int l, int r) {
    int ret = 0;
    for(int i = l; i<=r; i++)
        for(int j = i+1; j<=r; j++)
            if(A[j] < A[i]) ret ++;
    return ret;
}
void initialize () {
    memcpy(linr, A, sizeof linr);
    sort(linr+1, linr+N+1);
    len = (unique(linr+1, linr+N+1)-linr)-1;
    for(int i = 1; i<=N; i++)
        A[i] = lower_bound(linr+1, linr+len+1, A[i])-linr;
    qsize = 64;
    for(int i = 1; i<=N;) {
        ++qtot; int j;
        for(j = i; j-i<qsize && j<=N; j++)
            quads[qtot].push_back(A[j]);
        sort(quads[qtot].begin(), quads[qtot].end());
        qconflict[qtot] = getConflict(i, j-1);
        i = j;
    }
    for(int i = 1; i<=qtot; i++)
        for(int j = i+1; j<=qtot; j++) {
            int&sum = cconflict[i][j];
            vector<int>&v1 = quads[i], &v2 = quads[j];
            unsigned q = 0;
            int csum = 0;
            for(unsigned p = 0; p<v1.size(); p++) {
                while(q<v2.size() && v2[q] < v1[p]) q++, csum++;
                sum += csum;
            }
        }
    for(int i = 1; i<=qtot; i++)
        for(int j = i+1; j<=qtot; j++)
            cconflict[i][j] += cconflict[i][j-1];
    for(int r = qtot; r>=1; r--)
        for(int l = r; l>=1; l--)
            cvalue[l][r] = cvalue[l+1][r]+cconflict[l][r]-cconflict[l][l];
    for(int i = 1; i<=N; i++) PST::handleInsert(A[i]);
}
int query (int l, int r) {
    if(l >= r) return 0;
    int bl = (l-1)/qsize+1, br = (r-1)/qsize+1;
    int ret = 0;
    if(bl == br) {
        for(int i = l; i<r; i++)
            ret += PST::handleQuery(i+1, r, 1, A[i]-1);
        return ret;
    }
    ret = cvalue[bl+1][br-1];
    for(int i = bl+1; i<br; i++) ret += qconflict[i];
    int edgl = bl*qsize, edgr = (br-1)*qsize+1;
    for(int i = l; i<=edgl; i++) ret += PST::handleQuery(i+1, r, 1, A[i]-1);
    for(int i = edgr; i<=r; i++) ret += PST::handleQuery(edgl+1, i-1, A[i]+1, len); // ¼ÇµÃ·µ»Ø0!
    return ret;
}
inline int getInt () {
    int ret; char ch;
    while((ch = getchar()) < '0' || ch > '9') ;
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return ret;
}
int main () {
    N = getInt();
    for(int i = 1; i<=N; i++) A[i] = getInt();
    initialize();
    int M = getInt();
    int lastans = 0;
    for(int i = 1; i<=M; i++) {
        int a = getInt(), b = getInt();
        a ^= lastans, b ^= lastans;
        printf("%d\n", lastans = query(a, b));
    }
}