E题求条

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 10;

int n, m, a[N];
int tr[N], tr2[N];
int cnt[N];

int lowbit(int x) {
    return x & -x;
}

void update(int x, int c) {
    for (int i = x; i <= m - 1; i += lowbit(i)) 
        tr[i] += c;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) 
        res += tr[i];
    return res;
}

void update2(int x, int c) {
    for (int i = x; i <= m - 1; i += lowbit(i)) 
        tr2[i] += c;
}

int query2(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) 
        res += tr2[i];
    return res;
}


signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
	    cin >> a[i];
	    a[i] += a[i - 1];
	    cnt[a[i] % m]++;
	}
	int res = 0;
	for (int i = 1; i < m; i++)
	    res += cnt[i] * i;
	for (int i = 1; i <= n; i++) {
	    if ((a[i] % m == 0) || (a[i] % m == 1)) {
	        if (a[i] % m == 1) {
	            update(a[i] % m, a[i] % m), update2(a[i] % m, 1);
	        }
	        continue;
	    }
	    int tmp = query2(a[i] % m - 1) * (a[i] % m) - query(a[i] % m - 1);
	    res += tmp;
	    update(a[i] % m, a[i] % m), update2(a[i] % m, 1);
	}
	memset(tr, 0, sizeof tr);
	memset(tr2, 0, sizeof tr2);
	for (int i = n; i >= 1; i--) {
	    if ((a[i] % m == 0) || (a[i] % m == 1)) {
	        if (a[i] % m == 1) {
	            update(a[i] % m, a[i] % m), update2(a[i] % m, 1);
	        }
	        continue;
	    }
	    int tmp = query2(a[i] % m - 1) * (a[i] % m) - query(a[i] % m - 1);
	    res += m * query2(a[i] % m - 1) - tmp;
	    update(a[i] % m, a[i] % m), update2(a[i] % m, 1);
	}
	cout << res << '\n';
	return 0;
}