# 树状数组打卡()-其他

## 树状数组打卡()

### 1.楼兰图腾

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
ll resA, resV;
ll vl[N], vr[N], al[N], ar[N];
int tr[N], a[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1;i <= n; i++)
{
cin >> a[i];
change(a[i], 1);
}
memset(tr, 0, sizeof tr);
for(int i = n;i;i --)
{
change(a[i], 1);
}
for(int i = 1;i <= n;i ++)
resA += al[a[i]] * ar[a[i]], resV += vl[a[i]] * vr[a[i]];
cout << resV << ' ' << resA << '\n';
return 0;
}

### 2.一个简单的整数问题

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
int tr[N], a[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i];
while(m --)
{
char op;
cin >> op;
if(op == 'C')
{
int l, r, v;
cin >> l >> r >> v;
change(l, v);
change(r + 1, -v);
}
else
{
int x;
cin >> x;
cout << a[x] + ask(x) << '\n';
}
}
return 0;
}

### 3.一个简单的整数问题2

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
ll tr[2][N], a[N];
void change(int k, int x, int v)
{
while(x <= n)
{
tr[k][x] += v;
x += lbt(x);
}
}
{
ll res = 0;
while(x)
{
res += tr[k][x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i], a[i] += a[i - 1];
while(m --)
{
char op;
int l, r;
cin >> op >> l >> r;
if(op == 'C')
{
int v;
cin >> v;
change(0, l, v);
change(0, r + 1, -v);
change(1, l, l * v);
change(1, r + 1, -(r + 1) * v);
}
else
cout << a[r] + (r + 1) * ask(0, r) - ask(1, r) - a[l - 1] - l * ask(0, l - 1) + ask(1, l - 1) << '\n';
}
return 0;
}

### 4.谜一样的牛

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
int a[N], tr[N], pos[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 2; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) change(i, 1);
for(int i = n; i; i --)
{
int res = 0, l = 1, r = n;
while(l <= r)
{
int mid = l + r >> 1;
if(ask(mid) >= a[i] + 1) r = mid - 1, res = mid;
else l = mid + 1;
}
pos[i] = res;
change(res, -1);
}
for(int i = 1; i <= n; i ++) cout << pos[i] << '\n';
return 0;
}
————————

### 1.楼兰图腾

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
ll resA, resV;
ll vl[N], vr[N], al[N], ar[N];
int tr[N], a[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1;i <= n; i++)
{
cin >> a[i];
change(a[i], 1);
}
memset(tr, 0, sizeof tr);
for(int i = n;i;i --)
{
change(a[i], 1);
}
for(int i = 1;i <= n;i ++)
resA += al[a[i]] * ar[a[i]], resV += vl[a[i]] * vr[a[i]];
cout << resV << ' ' << resA << '\n';
return 0;
}

### 2.一个简单的整数问题

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
int tr[N], a[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i];
while(m --)
{
char op;
cin >> op;
if(op == 'C')
{
int l, r, v;
cin >> l >> r >> v;
change(l, v);
change(r + 1, -v);
}
else
{
int x;
cin >> x;
cout << a[x] + ask(x) << '\n';
}
}
return 0;
}

### 3.一个简单的整数问题2

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
ll tr[2][N], a[N];
void change(int k, int x, int v)
{
while(x <= n)
{
tr[k][x] += v;
x += lbt(x);
}
}
{
ll res = 0;
while(x)
{
res += tr[k][x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i], a[i] += a[i - 1];
while(m --)
{
char op;
int l, r;
cin >> op >> l >> r;
if(op == 'C')
{
int v;
cin >> v;
change(0, l, v);
change(0, r + 1, -v);
change(1, l, l * v);
change(1, r + 1, -(r + 1) * v);
}
else
cout << a[r] + (r + 1) * ask(0, r) - ask(1, r) - a[l - 1] - l * ask(0, l - 1) + ask(1, l - 1) << '\n';
}
return 0;
}

### 4.谜一样的牛

#include <bits/stdc++.h>
#define lbt(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
int a[N], tr[N], pos[N];
void change(int x, int v)
{
while(x <= n)
{
tr[x] += v;
x += lbt(x);
}
}
{
int res = 0;
while(x)
{
res += tr[x];
x -= lbt(x);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 2; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) change(i, 1);
for(int i = n; i; i --)
{
int res = 0, l = 1, r = n;
while(l <= r)
{
int mid = l + r >> 1;
if(ask(mid) >= a[i] + 1) r = mid - 1, res = mid;
else l = mid + 1;
}
pos[i] = res;
change(res, -1);
}
for(int i = 1; i <= n; i ++) cout << pos[i] << '\n';
return 0;
}