cogs 2569. [東方] 博丽灵梦 梦想妙珠

二次联通门 : cogs 2569. [東方] 博丽灵梦 梦想妙珠

/*

    cogs 2569. [東方] 博丽灵梦 梦想妙珠

    莫队水过。。

    好久没一遍AC了。。

    卡线上榜2333

*/

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cmath>

char Buf[], *buf = Buf;

int BUF = ;

void read (int &now)

{

    for (now = ; !isdigit (*buf); ++ buf);

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

}

#define Max 100000

int belong[Max];

struct Data

{

    int l, r, c, Id;

    bool operator < (const Data &now) const

    {

        return belong[this->l] == belong[now.l] ? this->r < now.r : belong[this->l] < belong[now.l];

    }

};

int count[Max <<  | ];

Data query[Max | ];

int number[Max | ];

int Answer[Max];

#define Cogs

int main (int argc, char *argv[])

{

#ifdef Cogs

    freopen ("mengxiangmiaozhu.in", "r", stdin);

    freopen ("mengxiangmiaozhu.out", "w", stdout);

    fread (buf, , BUF, stdin);

#endif

    int N, M;

    read (N);

    register int i;

    int x;

    int K_Size = sqrt (N);

    for (i = ; i <= N; ++ i)

        read (number[i]), belong[i] = (i + ) / K_Size;

    read (M);

    for (i = ; i <= M; ++ i)

    {

        read (query[i].l);

        read (query[i].r);

        read (query[i].c);

    }

    for (i = ; i <= M; ++ i)

        query[i].Id = i;

    std :: sort (query + , query +  + M);

    int l = , r = ;

    for (i = ; i <= M; ++ i)

    {

        for (; l < query[i].l; -- count[number[l]], ++ l);

        for (; l > query[i].l; -- l, ++ count[number[l]]);

        for (; r < query[i].r; ++ r, ++ count[number[r]]);

        for (; r > query[i].r; -- count[number[r]], -- r);

        Answer[query[i].Id] = count[query[i].c];

    }

    for (i = ; i <= M; ++ i)

        printf ("%d\n", Answer[i]);

    return ;

}