fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. #define MK 300005
  6. #define MN 100005
  7. #define Mod 1000000007
  8. typedef pair<int,int> P;
  9. typedef long long ll;
  10. int K, N, cnt, sum, x, y, now;
  11. int p[MK], f[MK], d1[MK], d2[MK], A[MN], B[MN], res[MN];
  12. vector <int> tn[MK];
  13. vector <P> tf[MK];
  14. int main() {
  15. 	int i, j;
  16. 	scanf("%d%d", &K, &N);
  17. 	for (i = 0; i < K; i++) scanf("%d", &p[i]);
  18. 	f[0] = now = 1;
  19. 	for (i = 1; i < K; i++) f[i] = (ll)f[i-1]*i%Mod;
  20. 	for (i = 0; i < N; i++) {
  21. 		scanf("%d%d", &A[i], &B[i]); A[i]--; B[i]--;
  22. 		tn[A[i]].push_back(i); tn[B[i]].push_back(i);
  23. 		tf[A[i]].push_back(P(i, p[B[i]])); tf[B[i]].push_back(P(i, p[A[i]]));
  24. 	}
  25. 	for (i = 0; i < K; i++) {
  26. 		cnt = p[i]-1, sum = 0;
  27. 		for (x = p[i]; x > 0; x -= x&-x) cnt -= d1[x];
  28. 		for (x = K-p[i]+1; x > 0; x -= x&-x) sum = (sum+d2[x])%Mod;
  29. 		now = (now+(ll)cnt*f[K-i-1])%Mod;
  30. 		for (vector<int>::iterator it = tn[i].begin(); it != tn[i].end(); ++it) {
  31. 			j = *it;
  32. 			res[j] = (res[j]-(ll)cnt*f[K-i-1])%Mod;
  33. 			res[j] = (res[j]-sum)%Mod;
  34. 		}
  35. 		for (vector<P>::iterator it = tf[i].begin(); it != tf[i].end(); ++it) {
  36. 			j = it->first; y = it->second;
  37. 			cnt = y-1; sum = 0;
  38. 			for (x = y; x > 0; x -= x&-x) cnt -= d1[x];
  39. 			for (x = K-y+1; x > 0; x -= x&-x) sum = (sum+d2[x])%Mod; 
  40. 			res[j] = (res[j]+(ll)cnt*f[K-i-1])%Mod;
  41. 			res[j] = (res[j]+sum)%Mod;
  42. 		}
  43. 		for (x = p[i]; x <= K; x += x&-x) d1[x] += 1;
  44. 		for (x = K-p[i]+1; x <= K; x += x&-x) d2[x] = (d2[x]+f[K-i-1])%Mod;
  45. 	}
  46. 	for (i = 0; i < N; i++) {
  47. 		res[i] = (res[i]+now)%Mod;
  48. 		if (p[A[i]] < p[B[i]]) {
  49. 			res[i] = (res[i]-f[K-A[i]-1])%Mod;
  50. 			res[i] = (res[i]+f[K-B[i]-1])%Mod;
  51. 		}
  52. 		if (res[i] < 0) res[i] += Mod;
  53. 		printf("%d\n", res[i]);
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 16192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/e0fCUf
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!