代码板子整理:P

Posted on Edited on

快读快写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int I(){
	int q=0;
	bool b=0;
	char c=getchar();
	while(c<'0'||c>'9')
	b = c=='-',c=getchar();
	while(c>='0'&&c<='9')
	q=q*10+c-'0',c=getchar();
	return b? -q:q;
}
void O(int x){
	if(x<0)
	putchar('-'),x=-x;
	if(x>=10)
	O(x/10);
	putchar(x%10+'0');
}

线段树 (lazy tag)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int n,m;
#define lc (p<<1)
#define rc (p<<1|1)
ll w[N];
struct node{
	ll l,r,sum,add;
}t[N*4];
void build(int p,int l,int r){
	t[p]={l,r,w[l],0};
	if(l==r) return;
	int m=(l+r)>>1;
	build(lc,l,m);
	build(rc,m+1,r);
	t[p].sum=t[lc].sum+t[rc].sum;
	return;
}
void pushup(int p){	
	t[p].sum=t[rc].sum+t[lc].sum;
}
void pushdown(int p){
	if(t[p].add){
		t[rc].sum+=t[p].add*(t[rc].r-t[rc].l+1);
		t[lc].sum+=t[p].add*(t[lc].r-t[lc].l+1);
		t[lc].add+=t[p].add;
		t[rc].add+=t[p].add;
		t[p].add=0;
	}
}
void update(int  p,int x,int y,ll k){
	if(x<=t[p].l&&t[p].r<=y){
		t[p].sum+=(t[p].r-t[p].l+1)*k;
		t[p].add+=k;
		return;
	}
	int m=(t[p].l+t[p].r)>>1;
	pushdown(p);
	if(x<=m) update(lc,x,y,k);
	if(y>m) update(rc,x,y,k);
	pushup(p);
}
ll query(int p,int x,int y){
	if(x<=t[p].l&&t[p].r<=y)
	return t[p].sum;
	int m=(t[p].l+t[p].r)>>1;
	ll sum=0;
	pushdown(p);
	if(x<=m) sum+=query(lc,x,y);
	if(y>m) sum+=query(rc,x,y);
	return sum;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
	build(1,1,n);
	while(m--){
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			update(1,x,y,k);
		}else{
			cout<<query(1,x,y)<<'\n';
		}
	}
	return 0;
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

NOIP祝福（雾）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define I_ak_ioi using namespace std;
I_ak_ioi; 
struct NOIP{
	int rp;
	int score;
	int rank;
}NOIP2018;
int main()
{
	while(19260817)
	{
		++NOIP2018.rp;
		NOIP2018.score=AK;
		NOIP2018.rank=1;
	}
	return 0;
}

埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> prime;
bool is_prime[N];

void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  // i * i <= n 说明 i <= sqrt(n)
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}