2022.11.24()

来了收拾了一阵QQ。

鬼知道为什么收拾它。

$ $

感觉今天出题出的很不地道,给我一种我能做出来的错觉,但是浪费了我的感情和时间。

粘都懒得粘。

$ $

我留下的奶茶大杯子被打扫卫生的阿姨扔了,难过!

树状数组

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x)
#define int long long 

using namespace std;
const int maxn = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, q, a[maxn], t[maxn];
void updata(int i, int k)
{
	while(i <= n) {t[i] += k; i += lowbit(i);}
}
void build(int x)
{
	for(int i = 1; i <= n; i++) updata(i, a[i]);
}
int sum(int x)
{
	int ans = 0;
	while(x != 0) {ans += t[x]; x -= lowbit(x);}
	return ans;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), q = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	build(n);
	for(int i = 1; i <= q; i++)
	{
		int op = read();
		if(op == 1)
		{
			int x = read(), k = read();
			updata(x,  k);
		}
		else
		{
			int x = read(), y = read();
			int ans1 = sum(x - 1), ans2 = sum(y);
			print(ans2 - ans1); puts("");
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:2022.11.24
Source:LOJ
knowledge:树状数组 
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x)

using namespace std;
const int maxn = 32010;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, t[maxn], v[maxn];
void add(int x)
{
	while(x < maxn) {t[x]++; x += lowbit(x);}
}
int sum(int x)
{
	int res = 0;
	while(x > 0) {res += t[x]; x -= lowbit(x);}
	return res;
}
int main()
{
	//freopen(".in", "r", stdin);    
	//freopen(".out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) 
	{
		int x = read(), y = read();
		int val = sum(x + 1);
		v[val]++;
		add(x + 1);
	}
	for(int i = 0; i < n; i++) print(v[i]), puts("");
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:2022.11.24
Source:LOJ
knowledge:  
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x) 

using namespace std;
const int maxn = 5e5 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, k, t[maxn];
int sum(int x)
{
	int res = 0;
	while(x > 0) {res += t[x]; x -= lowbit(x);}
	return res;
}
void add(int x, int val)
{
	while(x <= n) {t[x] += val; x += lowbit(x);}
}
void del(int x, int val)
{
	while(x <= n) {t[x] -= val; x += lowbit(x);}
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), k = read();
	for(int i = 1; i <= k; i++)
	{
		char ch;
		cin >> ch;
		if(ch == 'A')
		{
			int m = read();
			print(sum(m)); puts("");
		}
		if(ch == 'B')
		{
			int m = read(), p = read();
			add(m, p);
		}
		if(ch == 'C')
		{
			int m = read(), p = read();
			del(m, p);
		}
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

RMQ

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";

using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, m, a[maxn][21], lg[maxn]; 
void init()
{
	for(int i = 1; i <= n; i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);	
}
int query(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Max(a[l][k], a[r - (1 << k) + 1][k]);
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), m = read();
	init();
	for(int i = 1; i <= n; i++) a[i][0] = read();
	for(int j = 1; j <= 21; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
	   	a[i][j] = Max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
	for(int i = 1; i <= m; i++)
	{
		int l = read(), r = read();
		print(query(l, r)); puts("");
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define int long long 

using namespace std;
const int maxn = 1e5 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, k, a[maxn], b[maxn][21], c[maxn][21], lg[maxn];
void init()
{
	for(int i = 1; i <= n; i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
} 
int query1(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Max(b[l][k], b[r - (1 << k) + 1][k]);
} 
int query2(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Min(c[l][k], c[r - (1 << k) + 1][k]);
} 
signed main()
{
	//freopen(".in", "r", stdin); 
	//freopen(".out", "w", stdout);
	n = read(), k = read();
	for(int i = 1; i <= n; i++) b[i][0] = c[i][0] = a[i] = read();
	init();
	for(int j = 1; j <= 21; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
		{
			b[i][j] = Max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
			c[i][j] = Min(c[i][j - 1], c[i + (1 << (j - 1))][j - 1]);
		}
	for(int i = 1; i + k - 1 <= n; i++) 
		printf("%lld %lld\n", query1(i, i + k - 1), query2(i, i + k - 1));
	
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

线段树

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define int long long 
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;
const int maxn = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, q, a[maxn];
struct tree{
	int l, r, sum;
}t[maxn << 2];
void push_up(int rt)
{
	t[rt].sum = t[ls].sum + t[rs].sum;
}
void build(int rt, int l, int r)
{
	t[rt].l = l, t[rt].r = r;
	if(t[rt].l == t[rt].r) {t[rt].sum = a[l]; return ;}
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
	push_up(rt);
}
void updata(int rt, int x, int val)
{
	if(t[rt].l == x && t[rt].r == x) 
	{
		t[rt].sum += val;
		return ;
	}
	int mid = (t[rt].l + t[rt].r) >> 1;
	if(x <= mid) updata(ls, x, val);
	else updata(rs, x, val);
	push_up(rt);
}
int query(int rt, int l, int r)
{
	if(t[rt].l >= l && t[rt].r <= r) return t[rt].sum;
	int mid = (t[rt].l + t[rt].r) >> 1, ans = 0;
	if(l <= mid) ans += query(ls, l, r);
	if(r > mid) ans += query(rs, l, r);
	return ans;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), q = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	build(1, 1, n); 
	for(int i = 1; i <= q; i++)
	{
		int opt = read();
		if(opt == 1)
		{
			int x = read(), val = read();
			updata(1, x, val);
		}	
		else 
		{
			int l = read(), r = read();
			print(query(1, l, r)); puts(" "); 
		} 
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

————————

来了收拾了一阵QQ。

鬼知道为什么收拾它。

$ $

感觉今天出题出的很不地道,给我一种我能做出来的错觉,但是浪费了我的感情和时间。

粘都懒得粘。

$ $

我留下的奶茶大杯子被打扫卫生的阿姨扔了,难过!

树状数组

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x)
#define int long long 

using namespace std;
const int maxn = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, q, a[maxn], t[maxn];
void updata(int i, int k)
{
	while(i <= n) {t[i] += k; i += lowbit(i);}
}
void build(int x)
{
	for(int i = 1; i <= n; i++) updata(i, a[i]);
}
int sum(int x)
{
	int ans = 0;
	while(x != 0) {ans += t[x]; x -= lowbit(x);}
	return ans;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), q = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	build(n);
	for(int i = 1; i <= q; i++)
	{
		int op = read();
		if(op == 1)
		{
			int x = read(), k = read();
			updata(x,  k);
		}
		else
		{
			int x = read(), y = read();
			int ans1 = sum(x - 1), ans2 = sum(y);
			print(ans2 - ans1); puts("");
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:2022.11.24
Source:LOJ
knowledge:树状数组 
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x)

using namespace std;
const int maxn = 32010;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, t[maxn], v[maxn];
void add(int x)
{
	while(x < maxn) {t[x]++; x += lowbit(x);}
}
int sum(int x)
{
	int res = 0;
	while(x > 0) {res += t[x]; x -= lowbit(x);}
	return res;
}
int main()
{
	//freopen(".in", "r", stdin);    
	//freopen(".out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) 
	{
		int x = read(), y = read();
		int val = sum(x + 1);
		v[val]++;
		add(x + 1);
	}
	for(int i = 0; i < n; i++) print(v[i]), puts("");
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:2022.11.24
Source:LOJ
knowledge:  
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define lowbit(x) x & (-x) 

using namespace std;
const int maxn = 5e5 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, k, t[maxn];
int sum(int x)
{
	int res = 0;
	while(x > 0) {res += t[x]; x -= lowbit(x);}
	return res;
}
void add(int x, int val)
{
	while(x <= n) {t[x] += val; x += lowbit(x);}
}
void del(int x, int val)
{
	while(x <= n) {t[x] -= val; x += lowbit(x);}
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), k = read();
	for(int i = 1; i <= k; i++)
	{
		char ch;
		cin >> ch;
		if(ch == 'A')
		{
			int m = read();
			print(sum(m)); puts("");
		}
		if(ch == 'B')
		{
			int m = read(), p = read();
			add(m, p);
		}
		if(ch == 'C')
		{
			int m = read(), p = read();
			del(m, p);
		}
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

RMQ

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";

using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, m, a[maxn][21], lg[maxn]; 
void init()
{
	for(int i = 1; i <= n; i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);	
}
int query(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Max(a[l][k], a[r - (1 << k) + 1][k]);
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), m = read();
	init();
	for(int i = 1; i <= n; i++) a[i][0] = read();
	for(int j = 1; j <= 21; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
	   	a[i][j] = Max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
	for(int i = 1; i <= m; i++)
	{
		int l = read(), r = read();
		print(query(l, r)); puts("");
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define int long long 

using namespace std;
const int maxn = 1e5 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, k, a[maxn], b[maxn][21], c[maxn][21], lg[maxn];
void init()
{
	for(int i = 1; i <= n; i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
} 
int query1(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Max(b[l][k], b[r - (1 << k) + 1][k]);
} 
int query2(int l, int r)
{
	int k = lg[r - l + 1] - 1;
	return Min(c[l][k], c[r - (1 << k) + 1][k]);
} 
signed main()
{
	//freopen(".in", "r", stdin); 
	//freopen(".out", "w", stdout);
	n = read(), k = read();
	for(int i = 1; i <= n; i++) b[i][0] = c[i][0] = a[i] = read();
	init();
	for(int j = 1; j <= 21; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
		{
			b[i][j] = Max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
			c[i][j] = Min(c[i][j - 1], c[i + (1 << (j - 1))][j - 1]);
		}
	for(int i = 1; i + k - 1 <= n; i++) 
		printf("%lld %lld\n", query1(i, i + k - 1), query2(i, i + k - 1));
	
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

线段树

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#define orz cout << "AK IOI" << "\n";
#define int long long 
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;
const int maxn = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n, q, a[maxn];
struct tree{
	int l, r, sum;
}t[maxn << 2];
void push_up(int rt)
{
	t[rt].sum = t[ls].sum + t[rs].sum;
}
void build(int rt, int l, int r)
{
	t[rt].l = l, t[rt].r = r;
	if(t[rt].l == t[rt].r) {t[rt].sum = a[l]; return ;}
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
	push_up(rt);
}
void updata(int rt, int x, int val)
{
	if(t[rt].l == x && t[rt].r == x) 
	{
		t[rt].sum += val;
		return ;
	}
	int mid = (t[rt].l + t[rt].r) >> 1;
	if(x <= mid) updata(ls, x, val);
	else updata(rs, x, val);
	push_up(rt);
}
int query(int rt, int l, int r)
{
	if(t[rt].l >= l && t[rt].r <= r) return t[rt].sum;
	int mid = (t[rt].l + t[rt].r) >> 1, ans = 0;
	if(l <= mid) ans += query(ls, l, r);
	if(r > mid) ans += query(rs, l, r);
	return ans;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), q = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	build(1, 1, n); 
	for(int i = 1; i <= q; i++)
	{
		int opt = read();
		if(opt == 1)
		{
			int x = read(), val = read();
			updata(1, x, val);
		}	
		else 
		{
			int l = read(), r = read();
			print(query(1, l, r)); puts(" "); 
		} 
	} 
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}