acwing_kai

2206

acwing_kai
14小时前

### 前缀和 差分

/**
* 树状数组
* 区间修改 区间查询
* 前缀和 差分
*/
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100005;
typedef long long ll;
int n, m;
ll sum[maxn], t1[maxn], t2[maxn];

for(; x <= n; x += x & -x) t1[x] += k;
}

ll ans = 0;
for(; x; x -= x & -x) ans += t1[x];
return ans;
}

for(; x <= n; x += x & -x) t2[x] += k;
}

ll ans = 0;
for(; x; x -= x & -x) ans += t2[x];
return ans;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m;
for(int i = 1, x; i <= n; ++ i){
cin >> x;
sum[i] = sum[i - 1] + x;
}

while(m --){
char op;
int l, r;
ll z;
cin >> op;
if(op == 'Q'){
cin >> l >> r;
ll ans = sum[r] + (r + 1) * ask1(r) - ask2(r);
ans -= sum[l - 1] + l * ask1(l - 1) - ask2(l - 1);
cout << ans << endl;
}else{
cin >> l >> r >> z;
add2(r + 1, - (r + 1) * z);
}
}

return 0;
}


### 线段树 lazy标记

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
int l, r;
ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r){t[p].sum = a[l]; return; }
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

if(t[p].lazy){
t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
t[2 * p + 1].lazy += t[p].lazy;
t[p].lazy = 0;
}
}

void change(int p, int l, int r, ll d){
if(t[p].l >= l && t[p].r <= r) {
t[p].sum += d * (t[p].r - t[p].l + 1);
t[p].lazy += d;  //注意是 "+=" 不是 "="
return;
}
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) change(2 * p, l, r, d);
if(r > mid) change(2 * p + 1, l, r, d);
t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
if(t[p].l >= l && t[p].r <= r) return t[p].sum;
int mid = t[p].l + t[p].r >> 1;
ll res = 0;
if(l <= mid) res += ask(2 * p, l, r);
if(r > mid) res += ask(2 * p + 1, l, r);
return res;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
build(1, 1, n);

while(m --){
char op;
cin >> op;
if(op == 'Q'){
int l, r;
cin >> l >> r;
cout << ask(1, l, r) << endl;
}else{
int l, r;
ll val;
cin >> l >> r >> val;
change(1, l, r, val);
}
}
return 0;
}


### 分块

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100005;
int n, m, t;
int L[maxn], R[maxn], pos[maxn];

void change(int l, int r, ll d){
int lpos = pos[l], rpos = pos[r];
if(lpos == rpos){
for(int i = l; i <= r; ++ i) a[i] += d;
sum[lpos] += (r - l + 1) * d;
}else{
for(int i = l; i <= R[lpos]; ++ i) a[i] += d;
sum[lpos] += (R[lpos] - l + 1) * d;
for(int i = L[rpos]; i <= r; ++ i) a[i] += d;
sum[rpos] += (r - L[rpos] + 1) * d;
for(int i = lpos + 1; i < rpos; ++ i) add[i] += d;
}
}

ll query(int l, int r){
ll ret = 0;
int lpos = pos[l], rpos = pos[r];
if(lpos == rpos){
for(int i = l; i <= r; ++ i) ret += a[i];
ret += add[lpos] * (r - l + 1);
}else{
for(int i = lpos + 1; i < rpos; ++ i) ret += sum[i] + (R[i] - L[i] + 1) * add[i];
for(int i = l; i <= R[lpos]; ++ i) ret += a[i];
ret += add[lpos] * (R[lpos] - l + 1);
for(int i = L[rpos]; i <= r; ++ i) ret += a[i];
ret += add[rpos] * (r - L[rpos] + 1);
}
return ret;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
//分块
t = sqrt(n);
for(int i = 1; i <= t; ++ i){
L[i] = (i - 1) * sqrt(n) + 1;
R[i] = i * sqrt(n);
}
if(R[t] < n){
L[t + 1] = R[t] + 1;
R[t + 1] = n;
t ++;
}
//预处理
for(int i = 1; i <= t; ++ i){
for(int j = L[i]; j <= R[i]; ++ j){
pos[j] = i;
sum[i] += a[j];
}
}
//solve
while(m --){
char op;
cin >> op;
if(op == 'Q'){
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}else{
int l, r;
ll val;
cin >> l >> r >> val;
change(l, r, val);
}
}
}


/**
* 线段树
* 扫描线
* Lazy标记
*/

#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 100005;
int n, w, h, m;

struct Edge{
int x1, x2, y;
int val;
bool operator < (const Edge &tmp) const{
if(y != tmp.y) return y < tmp.y;
else return val < tmp.val; //可重叠 应先计算减少的再计算增加的
}
}e[maxn * 2];

struct SegmentTree{
int l, r, maxx, lazy;
}t[maxn * 8];

int XList[maxn * 2];
int query(int x){
return lower_bound(XList, XList + m, x) - XList;
}

void build(int p, int l, int r){
t[p].l = l, t[p].r = r, t[p].maxx = t[p].lazy = 0;
if(l == r) return;
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
}

if(t[p].lazy){
t[2 * p].maxx += t[p].lazy;
t[2 * p + 1].maxx += t[p].lazy;
t[2 * p].lazy += t[p].lazy;
t[2 * p + 1].lazy += t[p].lazy;
t[p].lazy = 0;
}
}

void change(int p, int l, int r, int val){
if(l <= t[p].l && t[p].r <= r){
t[p].maxx += val;
t[p].lazy += val;
return;
}
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) change(2 * p, l, r, val);
if(r > mid) change(2 * p + 1, l, r, val);

t[p].maxx = max(t[2 * p].maxx, t[2 * p + 1].maxx);
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> n >> w >> h){
int x, y, c, cnt = 0;
for(int i = 0; i < n; ++ i){
cin >> x >> y >> c;
e[cnt] = {x, x + w - 1, y, c};
XList[cnt ++] = x;
e[cnt] = {x, x + w - 1, y + h - 1, -c};
XList[cnt ++] = x + w - 1;
}

sort(XList, XList + cnt);
sort(e, e + cnt);

m = unique(XList, XList + cnt) - XList;
build(1, 0, m - 1);
int ans = 0;
for(int i = 0; i < cnt; ++ i){
int el = query(e[i].x1);
int er = query(e[i].x2);
change(1, el, er, e[i].val);
ans = max(ans, t[1].maxx);
}
cout << ans << endl;
}
}


#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100005;

struct Edge{
double x1, x2, y;
int op;
bool operator < (const Edge &tmp) const{
return y < tmp.y;
}
}e[maxn * 2];

struct SegmentTree{
int l, r, cnt;
double len;
}t[maxn * 4];

int n, m, T;
double xList[maxn * 2];

int query(double x){
return lower_bound(xList, xList + m, x) - xList;
}

void build(int p, int l, int r){
t[p].l = l, t[p].r = r, t[p].cnt = t[p].len = 0;
if(l == r) return;
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
}

void get_len(int p){
if(t[p].cnt >= 1) t[p].len = xList[t[p].r + 1] - xList[t[p].l];
else t[p].len = t[p << 1].len + t[(p << 1) | 1].len;
}

void update(int p, int l, int r, int val){
if(l <= t[p].l && t[p].r <= r){
t[p].cnt += val;
get_len(p);
return;
}
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) update(2 * p, l, r, val);
if(r > mid) update(2 * p + 1, l, r, val);
get_len(p);
}

int main(){
T = 1;
while(scanf("%d",&n), n){
double x1, y1, x2, y2;
int cnt = 0;
for(int i = 0; i < n; ++ i){
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
e[cnt] = {x1, x2, y1, 1};
xList[cnt ++] = x1;
e[cnt] = {x1, x2, y2, -1};
xList[cnt ++] = x2;
}

sort(xList, xList + cnt);
sort(e, e + cnt);
m = unique(xList, xList + cnt) - xList;

build(1, 0, m - 1);

double ans = 0;
for(int i = 0; i < cnt - 1; ++ i){
int el = query(e[i].x1);
int er = query(e[i].x2) - 1;
update(1, el, er, e[i].op);
ans += (e[i + 1].y - e[i].y) * t[1].len;
}

printf("Test case #%d\n", T ++);
printf("Total explored area: %.02f\n\n", ans);
}
return 0;
}


### 线段树基本操作

struct SegmentTree {
int l, r;
int dat;
}t[maxn * 4];

//1. 线段树的建树
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r){ t[p].dat = a[l]; return; }
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].dat = max(d[p * 2].dat, d[p * 2 + 1].dat);
}

build(1, 1, n);

//2. 线段树的单点修改
void change(int p, int x, int v){
if(t[p].l == t[p].r){ t[p].dat = v; return;}
int mid = (t[p].l + r[p].r) / 2;
if(x <= mid) change(p * 2, x, v);
else change(p * 2 + 1, x, v);
t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);
}

change(1, x, n);

//3. 线段树的区间查询
int ask(int p, int l, int r){
if(l <= t[p].l && t[p].r <= r) return t[p].dat;
int mid = t[p].l + t[p].r >> 1;
int res = -(1 << 30);
if(l <= mid) res = max(res, ask(2 * p, l, r));
if(r > mid) res = max(res, ask(2 * p + 1, l, r));
return res;
}
cout << ask(1, l, r) << endl;


### 延迟标记 lazy标记 Acwing.243

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
int l, r;
ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r){t[p].sum = a[l]; return; }
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

if(t[p].lazy){
t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
t[2 * p + 1].lazy += t[p].lazy;
t[p].lazy = 0;
}
}

void change(int p, int l, int r, ll d){
if(t[p].l >= l && t[p].r <= r) {
t[p].sum += d * (t[p].r - t[p].l + 1);
t[p].lazy += d;  //注意是 "+=" 不是 "="
return;
}
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) change(2 * p, l, r, d);
if(r > mid) change(2 * p + 1, l, r, d);
t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
if(t[p].l >= l && t[p].r <= r) return t[p].sum;
int mid = t[p].l + t[p].r >> 1;
ll res = 0;
if(l <= mid) res += ask(2 * p, l, r);
if(r > mid) res += ask(2 * p + 1, l, r);
return res;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
build(1, 1, n);

while(m --){
char op;
cin >> op;
if(op == 'Q'){
int l, r;
cin >> l >> r;
cout << ask(1, l, r) << endl;
}else{
int l, r;
ll val;
cin >> l >> r >> val;
change(1, l, r, val);
}
}
return 0;
}


### 扫描线例题 Acwing 247

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100005;

struct Edge{
double x1, x2, y;
int op;
bool operator < (const Edge &tmp) const{
return y < tmp.y;
}
}e[maxn * 2];

struct SegmentTree{
int l, r, cnt;
double len;
}t[maxn * 4];

int n, m, T;
double xList[maxn * 2];

int query(double x){
return lower_bound(xList, xList + m, x) - xList;
}

void build(int p, int l, int r){
t[p].l = l, t[p].r = r, t[p].cnt = t[p].len = 0;
if(l == r) return;
int mid = l + r >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
}

void get_len(int p){
if(t[p].cnt >= 1) t[p].len = xList[t[p].r + 1] - xList[t[p].l];
else t[p].len = t[p << 1].len + t[(p << 1) | 1].len;
}

void update(int p, int l, int r, int val){
if(l <= t[p].l && t[p].r <= r){
t[p].cnt += val;
get_len(p);
return;
}
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) update(2 * p, l, r, val);
if(r > mid) update(2 * p + 1, l, r, val);
get_len(p);
}

int main(){
T = 1;
while(scanf("%d",&n), n){
double x1, y1, x2, y2;
int cnt = 0;
for(int i = 0; i < n; ++ i){
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
e[cnt] = {x1, x2, y1, 1};
xList[cnt ++] = x1;
e[cnt] = {x1, x2, y2, -1};
xList[cnt ++] = x2;
}

sort(xList, xList + cnt);
sort(e, e + cnt);
m = unique(xList, xList + cnt) - xList;

build(1, 0, m - 1);

double ans = 0;
for(int i = 0; i < cnt - 1; ++ i){
int el = query(e[i].x1);
int er = query(e[i].x2) - 1;
update(1, el, er, e[i].op);
ans += (e[i + 1].y - e[i].y) * t[1].len;
}

printf("Test case #%d\n", T ++);
printf("Total explored area: %.02f\n\n", ans);
}
return 0;
}


#include <bits/stdc++.h>

using namespace std;

int state, now, ans, res;

void change(int pos){
//    for(int i = 0; i < 16; ++ i) cout << (now >> i & 1) << " ";
//    cout << endl;

int x = pos / 4, y = pos % 4;
for(int i = 0; i < 4; ++ i){
int p = x * 4 + i;
now = now ^ (1 << p);
}

for(int i = 0; i < 4; ++ i){
int p = 4 * i + y;
now = now ^ (1 << p);
}
now = now ^ (1 << pos);

//    for(int i = 0; i < 16; ++ i) cout << (now >> i & 1) << " ";
//    cout << endl;
}

int main(){
for(int i = 0; i < 4; ++ i){
string s;
cin >> s;
for(int j = 0; j < 4; ++ j){
if(s[j] == '+') state += (1 << (i * 4 + j));
}
}

ans = 0x3f3f3f3f;
for(int i = 0; i < (1 << 16); ++ i){
now = state;
int cnt = 0;
for(int j = 0; j < 16; ++ j){
if(i >> j & 1) cnt ++, change(j);
}
if(now == 0){
if(cnt < ans){
ans = cnt;
res = i;
}
}
}

cout << ans << endl;
for(int i = 0; i < 16; ++ i)
if(res >> i & 1) cout << (i / 4) + 1 << " " << (i % 4) + 1 << endl;
return 0;
}


acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 205;
bool unreach[maxn][maxn], vis[maxn];
int match[maxn];
int n, m, t;

bool dfs(int x){
for(int i = 1; i <= m; ++ i){
if(!vis[i] && !unreach[x][i]){
vis[i] = 1;
if(match[i] == 0 || dfs(match[i])){
match[i] = x;
return true;
}
}
}
return false;
}

int main(){
cin >> n >> m >> t;
for(int i = 0, x, y; i < t; ++ i){
cin >> x >> y;
unreach[x][y] = 1;
}
int ans = 0;
for(int i = 1; i <= n; ++ i){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans ++;
}
cout << ans << endl;
}


acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 105;
int n, t;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool valid[maxn][maxn], vis[maxn][maxn];
int match[maxn][maxn]; //match = xxxxxx = x * 1000 + y

bool ok(int x, int y){
if(x >= 1 && x <= n && y >= 1 && y <= n && valid[x][y] == 0) return true;
return false;
}

bool dfs(int x, int y){
for(int i = 0; i < 4; ++ i){
int xx = x + dx[i], yy = y + dy[i];
if(ok(xx,yy) && vis[xx][yy] == 0){
vis[xx][yy] = 1;
if(match[xx][yy] == 0 || dfs(match[xx][yy] / 1000, match[xx][yy] % 1000)){
match[xx][yy] = x * 1000 + y;
return true;
}
}
}
return false;
}

int main(){
cin >> n >> t;
for(int i = 1, x, y; i <= t; ++ i){
cin >> x >> y;
valid[x][y] = 1;
}
int ans = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
if((i + j) % 2 == 0 && valid[i][j] == 0){
memset(vis, 0, sizeof(vis));
if (dfs(i, j)) ans++;
}

cout << ans << endl;
}


acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 105;
int n, t;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool valid[maxn][maxn], vis[maxn][maxn];
int match[maxn][maxn]; //match = xxxxxx = x * 1000 + y

bool ok(int x, int y){
if(x >= 1 && x <= n && y >= 1 && y <= n && valid[x][y] == 0) return true;
return false;
}

bool dfs(int x, int y){
for(int i = 0; i < 4; ++ i){
int xx = x + dx[i], yy = y + dy[i];
if(ok(xx,yy) && vis[xx][yy] == 0){
vis[xx][yy] = 1;
if(match[xx][yy] == 0 || dfs(match[xx][yy] / 1000, match[xx][yy] % 1000)){
match[xx][yy] = x * 1000 + y;
return true;
}
}
}
return false;
}

int main(){
cin >> n >> t;
for(int i = 1, x, y; i <= t; ++ i){
cin >> x >> y;
valid[x][y] = 1;
}
int ans = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
if((i + j) % 2 == 0 && valid[i][j] == 0){
memset(vis, 0, sizeof(vis));
if (dfs(i, j)) ans++;
}

cout << ans << endl;
}


acwing_kai
1个月前
#include <bits/stdc++.h>

using namespace std;
const int maxn = 10005, maxm = 200005;
int n, m, e, tot, ans;
bool vis[maxn];
ver[++ tot] = y;
}

bool dfs(int x){
for(int i = head[x], y; i; i = Next[i]){
if(!vis[y = ver[i]]){
vis[y] = 1;
if(!match[y] || dfs(match[y])){
match[y] = x; return true;
}
}
}
return false;
}

int main(){
cin >> n >> m >> e;
for(int i = 1, x, y; i <= e; ++ i){
cin >> x >> y;
}

for(int i = 1; i <= n; ++ i){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans ++;
}

cout << ans << endl;
}


acwing_kai
1个月前
    //染色法判断二分图
#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 20005, maxm = 100005;
int head[maxn], ver[2 * maxm], Next[2 * maxm], tot, v[maxn];

ver[++ tot] = y;
}

bool dfs(int x, int color){
v[x] = color;
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(!v[y]){
bool flag = dfs(y, 3 - color);
if(!flag) return false;
}
else if(v[y] == color) return false;
}
return true;
}

bool check(){
memset(v, 0, sizeof(v));
for(int i = 1; i <= n; ++ i)
if(!v[i])
if(!dfs(i, 1)) return false;
return true;
}

int main()
{
cin >> n >> m;

for(int i = 1, x, y; i <= m; ++i){
cin >> x >> y;
}

cout << check() <<endl;
return 0;
}

/**
5 5
1 4
2 3
2 5
4 5
1 3
*/