#include <bits/stdc++.h>
#define lowbit(x) -x&x
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int tou[N], wei[N], n, m;
void add_tou(int i){
for (; i <= n; i += lowbit(i))
tou[i] ++;
}
int ask_tou(int i){
int res = 0;
for (; i; i -= lowbit(i))
res += tou[i];
return res;
}
void add_wei(int i){
for (; i <= n; i += lowbit(i))
wei[i] ++;
}
int ask_wei(int i){
int res = 0;
for (; i; i -= lowbit(i))
res += wei[i];
return res;
}
int main()
{
cin >> n >> m;
while (m -- ){
int op, l, r;
cin >> op >> l >> r;
if (op == 1)
add_tou(l), add_wei(r);
else
cout << ask_tou(r) - ask_wei(l - 1) << endl;
}
return 0;
}
#include <iostream>
typedef long long LL;
using namespace std;
const int N = 500010;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//归并的过程
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) tmp[k++] = q[i++];
else {
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
//扫尾
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
//物归原主
for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return res;
}
int main() {
//ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
cout << merge_sort(0, n - 1) << endl;
return 0;
}
#include <iostream>
typedef long long LL;
using namespace std;
const int N = 500010;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
//归并的过程
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) tmp[k++] = q[i++];
else {
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
//扫尾
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
//物归原主
for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return res;
}
int main() {
//ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
cout << merge_sort(0, n - 1) << endl;
return 0;
}