Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- #define BUFF_SIZE 1000002
- class OutParser {
- private:
- FILE *fout;
- char *buff;
- int sp;
- void write_ch(char ch) {
- if (sp == BUFF_SIZE) {
- fwrite(buff, 1, BUFF_SIZE, fout);
- sp = 0;
- buff[sp++] = ch;
- } else {
- buff[sp++] = ch;
- }
- }
- public:
- OutParser(const char* name) {
- fout = fopen(name, "w");
- buff = new char[BUFF_SIZE]();
- sp = 0;
- }
- ~OutParser() {
- fwrite(buff, 1, sp, fout);
- fclose(fout);
- }
- OutParser& operator << (int vu32) {
- if (vu32 <= 9) {
- write_ch(vu32 + '0');
- } else {
- (*this) << (vu32 / 10);
- write_ch(vu32 % 10 + '0');
- }
- return *this;
- }
- OutParser& operator << (long long vu64) {
- if (vu64 <= 9) {
- write_ch(vu64 + '0');
- } else {
- (*this) << (vu64 / 10);
- write_ch(vu64 % 10 + '0');
- }
- return *this;
- }
- OutParser& operator << (char ch) {
- write_ch(ch);
- return *this;
- }
- OutParser& operator << (const char *ch) {
- while (*ch) {
- write_ch(*ch);
- ++ch;
- }
- return *this;
- }
- };
- class InParser {
- private:
- FILE *fin;
- char *buff;
- int sp;
- char read_ch() {
- ++sp;
- if (sp == BUFF_SIZE) {
- sp = 0;
- fread(buff, 1, BUFF_SIZE, fin);
- }
- return buff[sp];
- }
- public:
- InParser(const char* nume) {
- fin = fopen(nume, "r");
- buff = new char[BUFF_SIZE]();
- sp = BUFF_SIZE - 1;
- }
- InParser& operator >> (int &n) {
- char c;
- while (!isdigit(c = read_ch()) && c != '-');
- int sgn = 1;
- if (c == '-') {
- n = 0;
- sgn = -1;
- } else {
- n = c - '0';
- }
- while (isdigit(c = read_ch())) {
- n = 10 * n + c - '0';
- }
- n *= sgn;
- return *this;
- }
- InParser& operator >> (long long &n) {
- char c;
- n = 0;
- while (!isdigit(c = read_ch()) && c != '-');
- long long sgn = 1;
- if (c == '-') {
- n = 0;
- sgn = -1;
- } else {
- n = c - '0';
- }
- while (isdigit(c = read_ch())) {
- n = 10 * n + c - '0';
- }
- n *= sgn;
- return *this;
- }
- };
- #ifdef LOCAL
- InParser fin("input.txt");
- #define fout cout
- #else
- InParser fin("dss.in");
- OutParser fout("dss.out");
- #define endl '\n'
- #endif
- const int NMAX = 4e5+5;
- const int QMAX = 1e4+5;
- const int MOD = 1e9+7;
- struct Query {
- int l, r, idx;
- };
- int n, m;
- int a[NMAX];
- int bucket[NMAX];
- Query q[QMAX];
- int fr[NMAX];
- int inv[NMAX];
- int qans[NMAX];
- void read() {
- fin >> n >> m;
- for (int i = 1; i <= n; i++)
- fin >> a[i];
- for (int i = 1; i <= m; i++) {
- fin >> q[i].l >> q[i].r;
- q[i].idx = i;
- }
- }
- int pow(int a, int n) {
- if(n == 0) return 1;
- if(n & 1) return 1ll * pow(a, n ^ 1) * a % MOD;
- int p = pow(a, n >> 1);
- return 1ll * p * p % MOD;
- }
- void precalc() {
- int sq = n / sqrt(m);
- for (int i = 1; i <= n; i++)
- bucket[i] = (i - 1) / sq + 1;
- sort(q + 1, q + m + 1, [](const Query &a, const Query &b) {
- if (bucket[a.l] == bucket[b.l]) return a.r < b.r;
- return a.l < b.l;
- });
- inv[1] = 1;
- }
- int inv_mod(int x) {
- if (inv[x]) return inv[x];
- return inv[x] = pow(x, MOD - 2);
- }
- void solve() {
- int l = 1, r = 1;
- fr[a[1]] = 1;
- int ans = 2;
- for (int i = 1; i <= m; i++) {
- while (q[i].l < l) {
- l--;
- fr[a[l]]++;
- ans = 1ull * ans * inv_mod(fr[a[l]]) * (fr[a[l]] + 1) % MOD;
- }
- while (r < q[i].r) {
- r++;
- fr[a[r]]++;
- ans = 1ull * ans * inv_mod(fr[a[r]]) * (fr[a[r]] + 1) % MOD;
- }
- while (l < q[i].l) {
- fr[a[l]]--;
- ans = 1ull * ans * inv_mod(fr[a[l]] + 2) * (fr[a[l]] + 1) % MOD;
- l++;
- }
- while (q[i].r < r) {
- fr[a[r]]--;
- ans = 1ull * ans * inv_mod(fr[a[r]] + 2) * (fr[a[r]] + 1) % MOD;
- r--;
- }
- qans[q[i].idx] = (1ll * ans - 1 + MOD) % MOD;
- }
- for (int i = 1; i <= m; i++) {
- fout << qans[i] << endl;
- }
- }
- int main() {
- read();
- precalc();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement