这周主要学习了线段树，基本能用线段树解决一些简单的题目。
D - Flat Subsequence
题意：单点修改+区间查询
代码
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define PII pair<int,int>
#define PIII pair<int,PII>
#define double long double
#define lson u<<1
#define rson u<<1|1
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int N = 3e5 + 5, SZ = N << 2;
int val[N];
int a[N], pos[N], n, k;
vector<int>dp(N), dp1(N);
struct node {
int mx, l, r;
} t[SZ];
void pushup(int u) {
t[u].mx = max(t[lson].mx, t[rson].mx);
}
void build(int l = 1, int r = N, int u = 1) {
t[u].l = l;
t[u].r = r;
if (l == r) {
pos[l] = u;
t[u].mx = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, lson);
build(mid + 1, r, rson);
pushup(u);
}
void add(int l, int x) {
int u = pos[l];
if (t[u].mx < x) {
t[u].mx = x;
while (u >>= 1)pushup(u);
}
}
int getmax(int L, int R, int l = 1, int r = N, int u = 1) {
if (L <= l && r <= R) {
return t[u].mx;
}
int mid = l + r >> 1;
int mx = 0;
if (L <= mid)mx = max(mx, getmax(L, R, l, mid, lson));
if (R > mid)mx = max(mx, getmax(L, R, mid + 1, r, rson));
pushup(u);
return mx;
}
void solve() {
int n;
cin >> n >> k;
build();
// cout<<n<<' '<<k<<endl;
for (int i = 1; i <= n; i++) {
cin>>val[i];
// val[i] = 1;
val[i]++;
int l = max(1ll, val[i] - k);
int r = min(N, val[i] + k);
int mx = getmax(l, r);
// cout<<"mx"<<mx<<endl;
add(val[i], mx + 1);
}
cout << getmax(1, N) << endl;
}
int32_t main() {
// std::ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
D. Traffic Jams in the Land
题意：单点修改+区间查询
代码
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define PII pair<int,int>
#define PIII pair<int,PII>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int N = 1e5 + 5, SZ = N << 2;
int n, m, k;
int a[N], pos[SZ];
struct data {
int val[60];
int l, r;
} t[SZ];
void pushup(int u) {
for (int i = 0; i < 60; i++) {
t[u].val[i] = t[u << 1].val[i] + t[u << 1 | 1].val[(i + t[u << 1].val[i]) % 60];
}
}
void build(int u = 1, int l = 1, int r = n) {
t[u].l = l;
t[u].r = r;
if (l == r) {
pos[l] = u;
for (int i = 0; i < 60; i++) {
t[u].val[i]++;
if (i % a[l] == 0) {
t[u].val[i]++;
}
}
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void add(int L, int v) {
int u = pos[L];
for (int i = 0; i < 60; i++) {
t[u].val[i] = 1;
if (i % v == 0) {
t[u].val[i]++;
}
}
while (u >>= 1)pushup(u);
}
int qsum(int L, int R, int T, int u = 1, int l = 1, int r = n) {
if (R < l || r < L) return 0;
if (L <= l && r <= R) {
return t[u].val[T % 60];
}
int mid = (l + r) >> 1;
int ans = 0;
if (L <= mid) ans = ans + qsum(L, R, T, u << 1, l, mid);
if (R > mid) ans = ans + qsum(L, R, T + ans, u << 1 | 1, mid + 1, r);
return ans;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build();
cin >> m;
for (int i = 0; i < m; i++) {
char x;
int l, r;
cin >> x >> l >> r;
if (x == 'A') {
cout << qsum(l, r - 1, 0) << endl ;
} else {
add(l, r);
}
}
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
仓鼠的鸡蛋
题意：将数据二分插入线段树
代码
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define PII pair<int,int>
#define PIII pair<int,PII>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int N = 3e5 + 5, SZ = N << 2;
int n, m, k;
int a[N],cnt[SZ];
struct data {
int mx,l,r;
} t[SZ];
void pushup(int u) {
t[u].mx = max(t[u << 1].mx , t[u << 1 | 1].mx);
}
void build(int u = 1, int l = 1, int r = n) {
t[u].l=l;t[u].r=r;
if (l == r) {
t[u].mx =m;
cnt[l]=0;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int add(int v, int u = 1, int l = 1, int r = n) {
while(t[u].l<t[u].r){
if(t[u<<1].mx>=v)u<<=1;
else u=(u<<1|1);
}
t[u].mx-=v;
int ans=t[u].l;
cnt[t[u].l]++;
if(cnt[t[u].l]>=k)t[u].mx=0;
while(u>>=1)pushup(u);
return ans;
}
void solve() {
cin >> n >> m >> k;
build();
for (int i = 1; i <= n; i++) {
int x;
cin>>x;
if(x<=m)cout<<add(x)<<endl;
else cout<<-1<<endl;
}
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
势能线段树模板题一
题意：势能线段树模版，感觉很难用得上。。
代码
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define PII pair<int,int>
#define PIII pair<int,PII>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int N = 2e5 + 5, SZ = N << 2;
int n, m, k;
int a[N], pos[SZ];
struct data {
int max, min,sum;
int tsq;
int l, r;
} t[SZ];
void pushup(int u) {
// cout<<"pp"<<endl;
t[u].sum=(t[u<<1].sum+t[u<<1|1].sum);
t[u].max=max(t[u<<1].max,t[u<<1|1].max);
t[u].min=min(t[u<<1].min,t[u<<1|1].min);
}
void build(int u = 1, int l = 1, int r = n) {
t[u].l = l;
t[u].r = r;
t[u].tsq=0;
if (l == r) {
pos[l] = u;
t[u].sum=a[l];
t[u].max=t[u].min=a[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void sq(int L, int R, int u = 1, int l = 1, int r = n) {
if(t[u].max<=1)return;
if(l==r){
t[u].max=sqrt(t[u].max);
t[u].min=sqrt(t[u].min);
t[u].sum=t[u].max;
return ;
}
int mid=l+r>>1;
if(L<=mid){
sq(L,R,u<<1,l,mid);
}
if(R>mid){
sq(L,R,u<<1|1,mid+1,r);
}
pushup(u);
}
int qsum(int L, int R, int u = 1, int l = 1, int r = n) {
// cout<<"qsum("<<L<<','<<R<<','<<T<<','<<u<<','<<l<<','<<r<<")"<<endl;
if (L <= l && r <= R) {
// cout<<'l'<<l<<r<<' '<<T<<endl;
// cout<<min(T,m)%k<<' '<<t[u].val[min(T,m)%k]<<endl;
// cout << "return " << t[u].val[min(T, m) % k] << endl;
return t[u].sum;
}
int mid = (l + r) >> 1;
int ans = 0;
if (L <= mid) {
ans = ans + qsum(L, R, u << 1, l, mid);
}
// cout<<'b'<<l<<' '<<r<<ans<<endl;
// cout<<"md"<<md<<endl;
if (R > mid) ans = ans + qsum(L, R, u << 1 | 1, mid + 1, r);
// cout<<'a'<<l<<' '<<r<<ans<<endl;
// cout << "return " << ans << endl;
return ans;
}
void solve() {
cin >> n >> m ;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build();
for (int i = 0; i < m; i++) {
int x;
int l, r;
cin >> x >> l >> r;
if (x == 1) {
sq(l, r);
} else {
cout << qsum(l, r) << endl;
}
}
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
10 5
10 10 10 10 10 10 10 10 10 10
1 1 7
2 1 10
1 4 10
2 1 1
1 1 10*/
标签：Week,7.14,10,int,SMU,long,build,mx,define From： https://www.cnblogs.com/ptlks/p/18302051