首页 > 其他分享 >2022.11.24

2022.11.24

时间：2022-11-25 08:55:05浏览次数：53  
标签：24 10 ch return int maxn include 2022.11

来了收拾了一阵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;
}

标签：24,10,ch,return,int,maxn,include,2022.11
From： https://www.cnblogs.com/yangchengcheng/p/16924096.html

相关文章

  • 20221124
    为什么越来越有种感觉，最终肯定会分开.如果知道结局，还有必要继续下去吗？两个人都没问题。那问题出在哪呢?我太喜欢吃醋了，又是对谁都很活泼开朗的，如果一开始就不认识还好，......
  • LeetCode刷题记录.Day24
    有效的括号20.有效的括号-力扣（LeetCode）classSolution{public:boolisValid(strings){if(s.size()%2!=0)returnfalse;//奇数必不符合......
  • 11.24.7
    #include<stdio.h>intmain(){ intn; scanf("%d",&n); switch(n/10) {case10:case9:printf("A");break; case8:printf("B");break; case7:printf("C");break......
  • 11.24.8
    #include<stdio.h>intmain(){ intn,i,j,a[10]; scanf("%d",&n); for(i=0;;i++) {if(n==0)break; a[i]=n%10; n=n/10; } printf("%d\n",i); for(j=i-1;j>=0;j--......
  • 2022-11-24 Acwing每日一题
    本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我......
  • 【2022-11-24】爬虫从入门到入狱(二)
    一、request高级用法1.1ssl认证#证书验证(大部分网站都是https)importrequestsres=requests.get('https://www.12306.cn')#如果是ssl请求,首先检查证书是否......
  • 11.24
    今日内容1.无符号、零填充2.非空3.默认值4.唯一值5.主键6.自增7.外键简介8.关系的判断9.一对多关系10.外键字段的建立11.多对多关系12一对一关系1.无符号、零......
  • 11.24.2
    #include<stdio.h>voidswap(int*pa,int*pb){intt;t=*pa; *pa=*pb;*pb=t;}intmain(){inta,b,*p1,*p2;scanf("%d%d",&a,&b);p1=&a;p2=&b;swa......
  • 11.24.3
    #include<stdio.h>voidfun(ints[][10],intb[],int*p,intm,intn);intmain(){intp; intm,n,i,j,a[1000][10],b[1000]; scanf("%d%d",&m,&n); for(i=0;i<m......
  • 11.24.4
    #include<stdio.h>intfun(inta[],intb[],intx,int*y);intmain(){intm; intn,i,a[1000],b[1000]; scanf("%d",&n); for(i=0;i<n;i++) {scanf("%d",&a[i]);......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99