树状数组打卡()-其他

发表于： 3月 18, 2023 3月 18, 2023
分类：其他
标签：其他

树状数组打卡()

不想讲，直接放code了。

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 ask(int 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];
		al[a[i]] += ask(a[i] - 1), vl[a[i]] += ask(n) - ask(a[i]);
		change(a[i], 1);
	}
	memset(tr, 0, sizeof tr);
	for(int i = n;i;i --)
	{
		ar[a[i]] += ask(a[i] - 1), vr[a[i]] += ask(n) - ask(a[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 ask(int 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 ask(int k, int 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 ask(int 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;
}

————————

不想讲，直接放code了。

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 ask(int 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];
		al[a[i]] += ask(a[i] - 1), vl[a[i]] += ask(n) - ask(a[i]);
		change(a[i], 1);
	}
	memset(tr, 0, sizeof tr);
	for(int i = n;i;i --)
	{
		ar[a[i]] += ask(a[i] - 1), vr[a[i]] += ask(n) - ask(a[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 ask(int 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 ask(int k, int 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 ask(int 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;
}