View Code of Problem 3868

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod(1e9 + 7);
const ll INF(0x3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head


class Mo {
public:
	int l, r, ID, Be;
};

const int N(3e4+7);
int T;
int n, m, unit;
ll inv[N], ans, numGay;
int classroom[N], gay[N], out[N];
Mo q[N];

bool cmp(Mo a, Mo b) { return a.Be == b.Be ? a.r < b.r : a.l < b.l; }

inline ll getinv(int x) {
	return powmod(x, mod - 2);
}

//dex 需变化量， flag加/减（用正负1表示）
void revise(int dex, int flag) {
	if (flag == 1) {
		ans = ((ans * ++numGay) % mod * inv[++gay[classroom[dex]]]) % mod;
	}
	else {
		ans = ((ans * gay[classroom[dex]]--) % mod * inv[numGay--]) % mod;
	}
}

int main() {

	//初始化逆元表
	per(i, 1, N) {
		inv[i] = getinv(i);
	}

	while (scanf("%d%d", &n, &m) != EOF) {
		unit = sqrt(n);
		per(i, 1, n+1) {
			scanf("%d", &classroom[i]);
		}
		per(i, 1, m + 1) {
			scanf("%d%d", &q[i].l, &q[i].r);
			q[i].ID = i;
			q[i].Be = q[i].l / unit;
		}

		sort(q + 1, q + m + 1, cmp);

		int l = 1, r = 1;
		ans = 1;
		numGay = 1;
		mem(gay, 0);
		gay[classroom[1]] = 1;

		per(i, 1, m + 1) {
			while (r < q[i].r) { revise(r + 1, 1); r++; }
			while (l > q[i].l) { revise(l - 1, 1); l--; }
			while (r > q[i].r) { revise(r, -1); r--; }
			while (l < q[i].l) { revise(l, -1); l++; }

			out[q[i].ID] = ans;
		}

		per(i, 1, m + 1) {
			printf("%d\n", out[i]);
		}
	}
	return 0;
}