线段树开新坑：kuangbin带你飞
程序员文章站
2022-07-13 11:29:01
...
写在最前面的废话
这里I以前的题是暑假刚刚开始的时候在家写的，然后多校一波就荒废了
9月开头回家一波，重新填坑，= =，kuangbin带你飞的pdf，这才一半题，后面还有一波，蓝瘦，慢慢写吧，不写题怎么变的更强
单点更新
A:hdu1166敌兵布阵：单点增减，区间sum
cmy曾经这题疯狂TLE
后来发现是因为cin的原因，cin好慢的说
树状数组也可以做，zkw的暴力单点修改也可加速一波
树状数组
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
const int N=50500;
int tree[N],n,x,y;
string st;
void add(int k,int num){
while (k<=n){
tree[k]+=num;
k+=k&-k;
}
}
int read(int k){
int sum=0;
while (k){
sum+=tree[k];
k-=k&-k;
}
return sum;
}
int main(){
int T;scanf("%d",&T);
for (int cas=1;cas<=T;cas++){
scanf("%d",&n);
memset(tree,0,sizeof(tree));
for (int i=1;i<=n;i++){
scanf("%d",&x);
add(i,x);
}
scanf("\n");
printf("Case %d:\n",cas);
int k=0;
for (;cin>>st&&st[0]!='E';){
scanf("%d%d",&x,&y);
if (st[0]=='Q') printf("%d\n",read(y)-read(x-1));
else if (st[0]=='A')add(x,y);
else add(x,-y);
}
}
return 0;
} 暴力单点修改
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 7;
struct segmentTree
{
#define lc (t<<1)
#define rc (t<<1^1)
int sum[N], M;
inline void build(int n){
M = 1;
for (;M < n;) M <<= 1;
M--;
memset(sum, sizeof(sum), 0);
for (int i = 1+M; i <= n+M; i++){
scanf("%d", &sum[i]);
}
for (int t = M; t >= 1; t--){
sum[t] = sum[lc] + sum[rc];
}
}
void add(int t, int x){
for (sum[t+=M]+=x, t>>=1; t; t>>=1){
sum[t] = sum[lc] + sum[rc];
}
}
int query(int l, int r){
int ans = 0;
for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans += sum[l^1];
if ( r&1) ans += sum[r^1];
}
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _, n, x, y;
scanf("%d", &_);
for (int __ = 1; __<=_;__++){
printf("Case %d:\n", __);
scanf("%d", &n);
T.build(n);
getchar();
string st;
for (;cin >> st && st[0] != 'E';){
scanf("%d%d", &x, &y);
if (st[0] == 'A'){
T.add(x, y);
}else if (st[0] == 'S'){
T.add(x, -y);
}else{
printf("%d\n", T.query(x, y));
}
}
}
}B:HDU 1754 I Hate It单点替换，区间rmq
把上面的代码改几行
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 8e5 + 7;
struct segmentTree
{
#define lc (t<<1)
#define rc (t<<1^1)
int ma[N], M;
inline void build(int n){
M = 1;
for (;M < n;) M <<= 1;
M--;
memset(ma, sizeof(ma), 0);
for (int i = 1+M; i <= n+M; i++){
scanf("%d", &ma[i]);
}
for (int t = M; t >= 1; t--){
ma[t] = max(ma[lc], ma[rc]);
}
}
void update(int t, int x){
for (ma[t+=M] = x, t>>=1; t; t>>=1){
ma[t] = max(ma[lc], ma[rc]);
}
}
int query(int l, int r){
int ans = 0;
for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans = max(ans, ma[l^1]);
if ( r&1) ans = max(ans, ma[r^1]);
}
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _, n, m, x, y;
for (;~scanf("%d%d", &n, &m);){
T.build(n);
string st;
for (;m--;){
cin >>st;
scanf("%d%d", &x, &y);
if (st[0] == 'U'){
T.update(x, y);
}else{
printf("%d\n", T.query(x, y));
}
}
}
}C:HDU 1394 Minimum Inversion Number 逆序对
树状数组舒服
数字插入按顺序插入对应的位置，然后看这个位置后面有多少个数就有多少逆序对
单点修改，区间求和
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
struct binaryIndexTree
{
int val[N], n;
inline void init(int n){
this->n = n;
memset(val, 0, sizeof(val));
}
inline void add(int k, int num){
for (;k <= n;){
val[k] += num;
k += k&-k;
}
}
inline int sum(int k){
int sum = 0;
for (;k;){
sum += val[k];
k -= k&-k;
}
return sum;
}
} T;
int arr[N], n;
int main()
{
//freopen("in.txt", "r", stdin);
for (;~scanf("%d", &n);){
T.init(n);
int sum = 0;
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
arr[i]++;
sum += T.sum(n) - T.sum(arr[i] - 1);
T.add(arr[i], 1);
}
int ans = sum;
for (int i = 0; i < n; i++){
sum += (n - arr[i]) - (arr[i] - 1);
ans = min(ans, sum);
}
printf("%d\n", ans);
}
}D HDU 2795 Billboard单点查询修改
注意：h = min(h, n);
单点查询区间最大值，查询修改一体
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1^1
int val[N], M; // M: num of non-leaf nodes
// have an index of the array x
// x + M is the index of it in the tree
inline void build(int n, int w){
M = 1; while(M<n) M<<=1; M--;
// leaf nodes with values
for (int leaf = 1+M; leaf <= n+M; leaf++){
val[leaf] = w;
}
// leaf nodes which is null
for (int leaf = n+1+M; leaf <= (M<<1^1); leaf++){
val[leaf] = 0;
}
// non-leaf nodes(include root)
for (int rt = M; rt >= 1; rt--){
val[rt] = max(val[lc], val[rc]);
}
}
inline void pushUp(int rt){
val[rt] = max(val[lc], val[rc]);
}
inline int query(int x, int rt){
if (rt > M){
val[rt] -= x;
return rt - M;
}
int ans = (val[lc] >= x) ? query(x, lc) : query(x, rc);
pushUp(rt);
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int n, h, w, x;
for (;~scanf("%d%d%d", &h, &w, &n);){
h = min(h, n);
T.build(h, w);
for (;n--;){
scanf("%d", &x);
if (T.val[1] < x) puts("-1");
else printf("%d\n", T.query(x, 1));
}
}
return 0;
}E POJ 2828 Buy Tickets单点查询修改
跟上题很像，查询修改一体
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int ans[N], pos[N], jump[N];
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1^1
int val[N], M; // M: num of non-leaf nodes
// have an index of the array x
// x + M is the index of it in the tree
inline void build(int n){
M = 1; while(M<n) M<<=1; M--;
// leaf nodes with values
for (int leaf = 1+M; leaf <= n+M; leaf++){
val[leaf] = 1;
}
// leaf nodes which is null
for (int leaf = n+1+M; leaf <= (M<<1^1); leaf++){
val[leaf] = 0;
}
// non-leaf nodes(include root)
for (int rt = M; rt >= 1; rt--){
val[rt] = val[lc] + val[rc];
}
}
inline void pushUp(int rt){
val[rt] = val[lc] + val[rc];
}
inline void update(int pos, int jump, int rt){
if (rt > M){
val[rt]--;
ans[rt-M] = jump;
return;
}
if (val[lc] >= pos) update(pos, jump, lc);
else update(pos-val[lc], jump, rc);
pushUp(rt);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int n;
for (;~scanf("%d", &n);){
T.build(n);
for (int i = 1; i <= n; i++){
scanf("%d %d", &pos[i], &jump[i]);
pos[i]++;
}
for (int i = n; i >= 1; i--){
T.update(pos[i], jump[i], 1);
}
for (int i = 1; i < n; i++){
printf("%d ", ans[i]);
}
printf("%d\n", ans[n]);
}
return 0;
}F POJ 2886 Who Gets the Most Candies?反素数+单点操作
题意：
n个熊孩子每个人有个数字a[i]，首先k号熊孩子出圈，然后第k+a[i]个熊孩子出圈，一个环，可以绕很多圈，如果a[i]为正则顺时针数，反之逆时针，相当于一个变体的约瑟夫游戏，第i个出圈的熊孩子，有f[i]的得分，f[i]为i的因子个数
反正没人看的讲解：
分为两个部分：线段树模拟约瑟夫游戏+寻找1到n范围内因数数量最多的那个ans，约瑟夫游戏只要做到第ans个人出圈就好了
区间和的线段树，每个叶子节点为1，代表一个熊孩子，出圈置为0，
至于因子数量，my math is very poor，所以我搜了题解，看见标题里一群反素数，于是顺势百度了反素数，搜到反素数深度分析，第三道题正好就是这玩意，于是复制粘贴之（划掉），虽然到现在还不知道反素数是个什么玩意
似乎搜到的题解都是打表来解决的因数个数问题，
我真的debug了10个小时，心累
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e7 + 7;
const LL INF = ~0LL;
const int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
struct child{
char name[11];
int val;
inline void read(){scanf("%s %d\n", name, &val);}
}arr[N];
LL maxNum, ansPos, n;
void dfs(int dep, LL tmp, int num){
if (dep >= 16) return;
if (num > maxNum){
maxNum = num;
ansPos = tmp;
}
if (num == maxNum && ansPos > tmp) ansPos = tmp;
for (int i = 1; i < 63; i++){
if (n / prime[dep] < tmp) break;
dfs(dep+1, tmp *= prime[dep], num*(i+1));
}
}
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int val[N], M;
inline void build(int n){
M = 1; while(M<n) M<<=1; M--;
for (int leaf = 1+M; leaf <= n+M; leaf++) val[leaf] = 1;
for (int leaf = n+1+M; leaf <= (M<<1^1); leaf++) val[leaf] = 0;
for (int rt = M; rt >= 1; rt--) val[rt] = val[lc] + val[rc];
}
inline int update(int pos, int rt){
val[rt]--;
if (rt > M) return rt - M;
if (val[lc] >= pos) return update(pos, lc);
else return update(pos-val[lc], rc);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int &mod = T.val[1];
for (LL k; ~scanf("%lld%lld\n", &n, &k);){
for (int i = 1; i <= n; i++) arr[i].read();
T.build(n);
ansPos = INF;
maxNum = 0;
dfs(0, 1, 1);
int pos = 0;
for (int i = 1; i <= ansPos; i++){
pos = T.update(k, 1);
//printf("k = %lld, pos = %d, mod = %d\n", k, pos, mod);
if (mod == 0) break;
if (arr[pos].val>0) k = (k-1 + arr[pos].val) % mod;
else k = ((k + arr[pos].val) % mod + mod) % mod;
if (k == 0) k = mod;
}
printf("%s %lld\n", arr[pos].name, maxNum);
}
return 0;
}区间修改
G HDU 1698 Just a Hook屠夫的钩
dota配图好评！！！
区间修改，最后一下查询总sum
因为这个查询就一次，而且还就直接存在根节点，所以就直接输出了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e6 + 7;
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M, sum[N], tag[N];
// 这里相对于常见的线段树，多了一个M，
// M的实际含义为非叶子节点的数量，
// 原数组索引为x，在线段树数组中的索引就是 M + x
// 因此，build可以改为自底向上的build
// n个实际有效的叶子节点，M+1-n个空值的叶子节点
inline void build(int n){
M = 1; while(M<n) M<<=1; M--;
memset(tag, 0, sizeof(tag));
// leaf nodes with values
for (int leaf = 1+M; leaf <= n+M; leaf++){
sum[leaf] = 1;
}
// leaf nodes which is null
for (int leaf = n+1+M; leaf <= (M<<1^1); leaf++){
sum[leaf] = 0;
}
// non-leaf nodes(include root)
for (int rt = M; rt >= 1; rt--){
sum[rt] = sum[lc] + sum[rc];
}
}
inline void pushUp(int rt){
sum[rt] = sum[lc] + sum[rc];
}
inline void pushDown(int rt, int len){
if (!tag[rt]) return;
tag[lc] = tag[rc] = tag[rt];
sum[lc] = sum[rc] = tag[rt] * (len>>1);
tag[rt] = 0;
}
inline void update(int L, int R, int x, int l, int r, int rt){
//printf("update(%d, %d, %d, %d, %d, %d)\n", L, R, x, l, r, rt);
if (L <= l && r <= R){
tag[rt] = x;
sum[rt] = (r-l+1) * x;
return;
}
pushDown(rt, r-l+1);
int m = (l+r) >> 1;
if (L <= m) update(L, R, x, lson);
if (m < R) update(L, R, x, rson);
pushUp(rt);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _, n, q, l, r, x;
scanf("%d", &_);
for (int __ = 1; __ <= _; __++){
scanf("%d%d", &n, &q);
T.build(n);
for (;q--;){
scanf("%d%d%d", &l, &r, &x);
T.update(l, r, x, 1, T.M+1, 1);
}
printf("Case %d: The total value of the hook is %d.\n", __, T.sum[1]);
}
return 0;
}H POJ 3468 A Simple Problem with Integers 区间修改和查询
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 5e5 + 7;
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
LL M, sum[N], tag[N];
// 这里相对于常见的线段树，多了一个M，
// M的实际含义为非叶子节点的数量，
// 原数组索引为x，在线段树数组中的索引就是 M + x
// 因此，build可以改为自底向上的build
// n个实际有效的叶子节点，M+1-n个空值的叶子节点
inline void build(LL n){
M = 1; while(M<n) M<<=1; M--;
memset(tag, 0, sizeof(tag));
// leaf nodes with values
for (LL leaf = M+1; leaf <= n+M; leaf++){
scanf("%lld", &sum[leaf]);
}
// leaf nodes which is null
for (LL leaf = n+1+M; leaf <= (M<<1^1); leaf++){
sum[leaf] = 0;
}
// non-leaf nodes(include root)
for (LL rt = M; rt >= 1; rt--){
sum[rt] = sum[lc] + sum[rc];
}
}
inline void pushUp(LL rt){
sum[rt] = sum[lc] + sum[rc];
}
inline void pushDown(LL rt, LL len){
if (tag[rt] == 0) return;
tag[lc] += tag[rt];
tag[rc] += tag[rt];
sum[lc] += tag[rt] * (len>>1);
sum[rc] += tag[rt] * (len>>1);
tag[rt] = 0;
}
inline void update(LL L, LL R, LL x, LL l, LL r, LL rt){
//prLLf("update(%d, %d, %d, %d, %d, %d)\n", L, R, x, l, r, rt);
if (L <= l && r <= R){
tag[rt] += x;
sum[rt] += (r-l+1) * x;
return;
}
pushDown(rt, r-l+1);
LL m = (l + r) >> 1;
if (L <= m) update(L, R, x, lson);
if (m < R) update(L, R, x, rson);
pushUp(rt);
}
LL query(LL L, LL R, LL l, LL r, LL rt){
if (L <= l && r <= R) return sum[rt];
pushDown(rt, r-l+1);
LL m = (l + r) >> 1;
LL ans = 0;
if (L <= m) ans += query(L, R, lson);
if (m < R) ans += query(L, R, rson);
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
LL n, q, l, r, x;
char ch;
for (;~scanf("%lld%lld", &n, &q);){
T.build(n);
for (;q--;){
getchar();
scanf("%c%lld%lld", &ch, &l, &r);
if (ch == 'Q'){
printf("%lld\n", T.query(l, r, 1, T.M+1, 1));
} else {
scanf("%lld", &x);
T.update(l, r, x, 1, T.M+1, 1);
}
}
}
return 0;
}
I POJ 2528 Mayor’s posters 离散化姿势比较清奇
by cww97
因为这个图所以，不能当做左闭右开的线段树来做
and，卡了两个小时是因为
这个傻逼错误
//for (int i = 1; i <= A; i++) {
// x[a[i]] = i;//啊啊啊啊啊啊啊啊啊啊啊啊啊啊
//printf("x[%d] = %d\n", a[i], i);
//}
T.build(A);
for (int i = 1; i <= n; i++){
int L = lower_bound(a+1, a+A+1, l[i]) - a;//x[l[i]]
int R = lower_bound(a+1, a+A+1, r[i]) - a;//x[r[i]]
//printf("(%d, %d)\n", L, R);
T.update(L, R, i, 1, T.M+1,1);
}妈的离散化忘了用lower_bound，还开数组存
发现错误前怀疑数据
发现错误后被自己蠢哭
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;
int l[N], r[N], n;
int a[N], A, x[N];
bool vis[N];
int ans;
struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M, col[N];
inline void build(int n){
M = 1; while(M<n)M<<=1; M--;
memset(col, 0, sizeof(col));
}
inline void pushDown(int rt){
if (col[rt] == 0) return;
col[lc] = col[rc] = col[rt];
col[rt] = 0;
}
inline void update(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
col[rt] = x;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, x, lson);
if (m < R) update(L, R, x, rson);
}
inline int query(int rt){
if (col[rt] > 0) {
if (vis[col[rt]]) return 0;
vis[col[rt]] = 1;
return 1;
}
if (rt > M) return 0;
int ans = 0;
ans += query(lc);
ans += query(rc);
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _;
scanf("%d", &_);
for (;_--;){
scanf("%d", &n);
A = 0;
for (int i = 1; i <= n; i++){
scanf("%d%d", &l[i], &r[i]);
a[++A] = l[i];
a[++A] = r[i];
}
sort(a + 1, a + A+1);
A = unique(a + 1, a + A+1) - (a + 1);
for (int i = A; i > 1; i--){
if (a[i-1] + 1 < a[i]) a[++A] = a[i-1] + 1;
}
sort(a + 1, a + A+1);
T.build(A);
for (int i = 1; i <= n; i++){
int L = lower_bound(a+1, a+A+1, l[i]) - a;
int R = lower_bound(a+1, a+A+1, r[i]) - a;
T.update(L, R, i, 1, T.M+1,1);
}
ans = 0;
memset(vis, 0, sizeof(vis));
printf("%d\n", T.query(1));
}
return 0;
}J POJ 3225 Help with Intervals 双标记线段树
1.关于集合运算的推导规约，知道集合是什么东西就一定会推导！
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
2.倍化区间处理开闭区间的问题。因为普通的线段树实际处理的并非真正的区间，而是一系列点，相当于处理一个向量。这个问题需要处理的是真正的区间，所以应该有一个主导思想就是，把区间点化！不知哪位大牛搞了一个倍增区间出来，实在佩服！对于待处理区间a,b，对其边界均乘2。若区间左开则对左界值+1，若区间右开，则对右界-1！
如：[2,3]会倍增为[4,6]，[2,3)会倍增为[4,5]，（2,3]会倍增为[5,6]，(2,3)将倍增为[5,5]，我们这时可以看到，对于普通线段树无法处理的线段如(x,x+1)将被点化为[2*x+1,2*x+1]！这个问题得到比较完美的解决
最后把查找出来的区间逆向倍增操作一下，就可以得到实际的区间以及起开闭情况！
代码中还将用到延迟更新，向子节点更新操作时，这个具体纠结在互换上面，不过仔细想想还是容易理解的，下面代码会有注解！
本题包含区间01赋值和区间01取反
一开始准备tree当做值，lazy当做是否取反的标记
wa了，lj跟我抱怨：你就不能老老实实写个双标记线段树吗
好的，双标记，反正最后我query到所有的叶子节点，两个标记亦或一下就是值，狗拿耗子，猫下岗了，tree后来，看起来是值，其实是另一个标记，不需要pushUp反正没有区间查询
本题略考验代码能力，很容易WA哭（比如我自己（划掉）），百度到的大部分题解都是学的kuangbin的写法，一个update，update里面分5个大if，我的是在main里面if，线段树就两个功能，区间赋值和取反，剩下的交给int main来组织
铭记一点，老老实实写双标记，别搞骚操作
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 131072 + 7;
int ans[N];
struct segTree{
#define lc rt<<1
#define rc rt<<1^1
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int tree[N<<1], lazy[N<<1];
inline void build(){
memset(lazy, 0, sizeof(lazy));
memset(tree, 0, sizeof(tree));
}
inline void pushDown(int rt){
if (tree[rt] != -1){ // -1: mixture
tree[lc] = tree[rc] = tree[rt];
lazy[lc] = lazy[rc] = 0;
}
if (lazy[rt]){
if (tree[lc] != -1) tree[lc] ^= 1;
else lazy[lc] ^= 1;
if (tree[rc] != -1) tree[rc] ^= 1;
else lazy[rc] ^= 1;
lazy[rt] = 0;
}
tree[rt] = -1;
}
void setval(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R) {
tree[rt] = val;
lazy[rt] = 0;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) setval(L, R, val, lson);
if (m < R) setval(L, R, val, rson);
}
void invert(int L, int R, int l, int r, int rt){
if (L <= l && r <= R){
if (tree[rt] != -1) tree[rt] ^= 1;
else lazy[rt] ^= 1;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) invert(L, R, lson);
if (m < R) invert(L, R, rson);
}
void query(int l, int r, int rt){
if (l == r){ // leaf
ans[l] = tree[rt] ^ lazy[rt];
return;
}
pushDown(rt);
int m = (l + r) >> 1;
query(lson);
query(rson);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
char op, lseg, rseg;
int l, r, n = 131072;
T.build();
for (;~scanf("%c %c%d,%d%c\n", &op, &lseg, &l, &r, &rseg);){
l <<= 1, r <<= 1;
if (lseg == '(') l++;
if (rseg == ')') r--;
//printf("--------> %c [%d, %d]\n", op, l, r);
if (l > r){
if (op == 'I' || op == 'C'){
T.setval(0, n, 0, 0, n, 1);
}
} else if (op == 'U'){ // S = S | T
T.setval(l, r, 1, 0, n, 1);
} else if (op == 'I'){ // S = S & T
if (l > 0) T.setval(0, l-1, 0, 0, n, 1);
if (r < n) T.setval(r+1, n, 0, 0, n, 1);
} else if (op == 'D'){ // S = S - T
T.setval(l, r, 0, 0, n, 1);
} else if (op == 'C'){ // S = T - S
T.invert(l, r, 0, n, 1);
if (l > 0) T.setval(0, l-1, 0, 0, n, 1);
if (r < n) T.setval(r+1, n, 0, 0, n, 1);
} else { // op == 'S': S = S^T = (S-T)|(T-S)
T.invert(l, r, 0, n, 1);
}
}
T.query(0, n, 1);
bool haveAns = 0, haveOne = 0;
for (int i = 0; i <= n; i++){
if (!haveOne && ans[i]){
if (haveAns) putchar(' ');
haveAns = haveOne = 1;
putchar(i&1 ? '(' : '[');
printf("%d,", i >> 1);
} else if (haveOne && !ans[i]){
printf("%d", i >> 1);
putchar((i-1)&1 ? ')' :']');
haveOne = 0;
}
}
if (!haveAns) puts("empty set");
else puts("");
return 0;
}K POJ 1436 Horizontally Visible Segments 区间染色
思路如同poj2777
不过这题的空间真的好极限
一个bool1字节
8000*8000/1024/1024 = 61MB
剩下的用来开线段树，一步留神就MLE
还有最后那个暴力的三重for循环居然没有TLE
不对我还是TLE了一发，
if (reach[k][i] && reach[k][j]) ans++;
这么写的话就会TLE，大概跟内存读写有一定关系
cpu访问高速缓存里的数据，不直接访问内存里的，所以，这个数组太大(60MB)没法整个丢进高速缓存里，只能一次丢个几行，前一种写法，第三重循环只会访问数组的i和j行，第三重循环每次都是缓存命中的，不会向内存再发请求，而后一种写法，k没变化一次，缓存就不命中一次，就好再装填缓存，然后就TLE了
操作系统真好玩，感谢钱卫宁和高明老师
这题，，太极限
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 8007;
struct line{
int l, r, x, id;
inline void read(int i){
scanf("%d%d%d", &l, &r, &x);
id = i, l <<= 1, r <<= 1;
}
bool operator < (const line &b) const {
return x < b.x;
}
} lines[N];
bool reach[N][N];
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int tree[N*8], n;
inline void build(){
n = 8000 * 2; // length of tree
memset(tree, 0, sizeof(tree));
}
inline void pushDown(int rt){
if (!tree[rt]) return;
tree[lc] = tree[rc] = tree[rt];
tree[rt] = 0;
}
void update(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R){
tree[rt] = val;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
}
void query(int L, int R, int id, int l, int r, int rt){
if (tree[rt]){
reach[tree[rt]][id] = 1;
return;
}
if (l == r) return;
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) query(L, R, id, lson);
if (m < R) query(L, R, id, rson);
}
inline void query(int l, int r, int id){
query(l, r, id, 0, n, 1);
}
inline void update(int l, int r, int val){
update(l, r, val, 0, n, 1);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _, n;
scanf("%d", &_);
for (; _--;){
scanf("%d", &n);
for (int i = 1; i <= n; i++) lines[i].read(i);
sort(lines + 1, lines + n + 1);
T.build();
memset(reach, 0, sizeof(reach));
for (int i = 1; i <= n; i++){
T.query(lines[i].l, lines[i].r, i);
T.update(lines[i].l, lines[i].r, i);
}
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) if (reach[i][j]){
for (int k = 1; k <= n; k++){
if (reach[i][k] && reach[j][k]) ans++;
}
}
}
printf("%d\n", ans);
}
return 0;
}
L POJ 2991 Crane 计算几何
题意：有一个吊车由很多个不同长度的线段组成，一开始是一条长直线起点在（0，0），尾节点在（0，sum[n]），每条线段之间的夹角的初始值是180度。然后有一些操作a、 b将第a条线段和a+1之间的夹角变成b度，经过每一次操作都要求出尾节点的坐标。
首先要用到一个计算几何的知识（没学过。。请教而来）：
对于一个向量x,y，逆时针旋转a度得到的新向量x’、y’，可以由如下推导
把每个线段认为是一个个向量，整体的endpoint就是所有向量的sum
如下结构体为线段树的节点
struct vec{
double x, y, a, lazy;// a is the angle between i and i-1
};很容易读错题的一点是：每次更新给的角度a不是旋转角度，而是s和s+1的夹角
所以旋转角度 ang = vec[s+1].a - a
update之后再更新vec[s+1] = a
线段树区间更新是将s+1到n旋转ang度
还有一个attention是：本题请使用C++提交，G++会TLE
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4e4 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-8;
int arr[N];
struct vec{
double x, y, a, lazy;// a is the angle between i and i-1
vec (){}
vec (double q, double w, double e, double r):x(q), y(w), a(e), lazy(r){}
vec operator + (const vec &V) const { // only no-leaf nodes get from +
return vec(x + V.x, y + V.y, a, 0); // so last 2 numbers no important
}
inline void tag(const double &ang){
double ox = x, oy = y; // old x&y
x = ox * cos(-ang) - oy * sin(-ang);// rotate
y = ox * sin(-ang) + oy * cos(-ang);
lazy += ang;
}
inline void print(){ // 0.0 YouYa
double px = fabs(x)<EPS ? 0 : x; // I don't want to see "-0.00"
double py = fabs(y)<EPS ? 0 : y;
printf("%.2lf %.2lf\n", px, py);
}
};
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M;
vec tree[N];
inline void build(const int &n){
M=1; for(;M<n;)M<<=1; if(M>1)M--;
memset(tree, 0, sizeof tree);
for (int len, i = 1; i <= M+1; i++){
tree[i+M] = vec(0, i<=n ? arr[i] : 0, PI, 0);
}
for (int rt = M; rt >= 1; rt--) {
tree[rt] = tree[lc] + tree[rc];
}
}
inline void pushDown(int rt){
if (fabs(tree[rt].lazy) < EPS) return;
tree[lc].tag(tree[rt].lazy);
tree[rc].tag(tree[rt].lazy);
tree[rt].lazy = 0;
}
void update(int L, int R, double val, int l, int r, int rt){
if (L <= l && r <= R){tree[rt].tag(val); return;}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
tree[rt] = tree[lc] + tree[rc];
}
inline void update(int l, int r, double val){
update(l, r, tree[l+M].a - val, 1, M+1, 1);
tree[l+M].a = val;//attention: val is the ang between l-1 and l
tree[1].print();
}
} T; // sometimes we need undef here
int main(){
//freopen("in.txt", "r", stdin);
bool firstT = 1;
for (int n, q; ~scanf("%d%d", &n, &q);){
if (!firstT) puts(""); firstT = 0;
for (int i = 1; i <= n; i++) scanf("%d", arr + i);
T.build(n);
for (int s, a; q--;){
scanf("%d%d", &s, &a);
T.update(s+1, n, PI * a / 180);
}
}
return 0;
}区间合并
M POJ 3667 Hotel 区间合并
题意:
1 a:询问是不是有连续长度为 a 的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:update:区间替换 query:询问满足条件的最左断点
在pushUp的时候合并左右连续的区间，第一次写，看了会kuangbin的写法
用for循环建成标准满二叉树，再define一下lc和rc，写的时候，真是舒服
想到了一个新的，关于线段树的，封装上的优化
// have relation with int main
inline void update(int l, int r, int val){
update(l, r, val, 1, M+1, 1);
}
inline int query(int len){
return query(len, 1, M+1, 1);
}没什么卵用，还可能被各位大佬或者压行型选手喷强行增加代码行数，不过这么写的时候，写int main几乎不用动脑子
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 65536 * 2 + 7;
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M;
int lsum[N], msum[N], rsum[N], lazy[N];
inline void build(const int &n){
M=1; for(;M<n;) M<<=1; if(M>1)M--;
memset(lazy,-1, sizeof lazy);
for (int i = 1; i <= M+1; i++){
lsum[i+M] = msum[i+M] = rsum[i+M] = i<=n ? 1 : 0;
}
for (int rt = M; rt >= 1; rt--) {
lsum[rt] = msum[rt] = rsum[rt] = msum[lc] + msum[rc];
}
}
inline void pushUp(int rt, int len){
lsum[rt] = lsum[lc];
rsum[rt] = rsum[rc];
if (lsum[rt] == len>>1) lsum[rt] += lsum[rc];
if (rsum[rt] == len>>1) rsum[rt] += rsum[lc];
msum[rt] = max(msum[lc], msum[rc]);
msum[rt] = max(msum[rt], rsum[lc] + lsum[rc]);
}
inline void pushDown(int rt, int len){
if (lazy[rt] == -1) return;
lazy[lc] = lazy[rc] = lazy[rt];
lsum[lc] = msum[lc] = rsum[lc] = lazy[rt] ? 0 : len>>1;
lsum[rc] = msum[rc] = rsum[rc] = lazy[rt] ? 0 : len>>1;
lazy[rt] = -1;
}
void update(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R){
lsum[rt] = msum[rt] = rsum[rt] = val ? 0 : r-l+1;
lazy[rt] = val;
return;
}
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
pushUp(rt, r-l+1);
}
int query(int len, int l, int r, int rt){
if (l == r) return l;
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (msum[lc] >= len) return query(len, lson);
else if (rsum[lc] + lsum[rc] >= len) return m-rsum[lc]+1;
else if (msum[rc] >= len) return query(len, rson);
return 0;
}
// have relation with int main
inline void update(int l, int r, int val){
update(l, r, val, 1, M+1, 1);
}
inline int query(int len){
return query(len, 1, M+1, 1);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
for (int n, q; ~scanf("%d%d", &n, &q);){
T.build(n);
for (int op, pos, len; q--;){
scanf("%d", &op);
if (op == 1){ // query
scanf("%d", &len);
printf("%d\n", pos = T.query(len));
if (pos) T.update(pos, pos+len-1, 1);
} else { // set
scanf("%d%d", &pos, &len);
T.update(pos, pos+len-1, 0);
}
}
}
return 0;
}N HDU 3308 LCIS 最大连续上升子序列
这种区间固定的题目，建满满二叉树是非常方便的
尤其是单点修改的时候，o（1）找到要修改点，而不是递归向下
这里直接找到然后log的复杂度pushUp就好了
比近期过的大部分稍微快那么一点，没那么明显，
最上面的是我的
样例挺好，过样例应该就能过了，区间合并，不知道非递归咋写，这里就搞个常规的query（只会这么写了）
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 262144 + 7;
int arr[N];
struct ZKWsegTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M;
int lnum[N], rnum[N];
int lsum[N], msum[N], rsum[N];
inline void pushUp(int rt, int len){
lnum[rt] = lnum[lc], rnum[rt] = rnum[rc];
lsum[rt] = lsum[lc], rsum[rt] = rsum[rc];
msum[rt] = max(msum[lc], msum[rc]);
if (rnum[lc] < lnum[rc]){
if (lsum[rt] == len>>1) lsum[rt] += lsum[rc];
if (rsum[rt] == len>>1) rsum[rt] += rsum[lc];
msum[rt] = max(msum[rt], rsum[lc] + lsum[rc]);
}
}
inline void build(const int &n){
M=1;for(;M<n;)M<<=1;if(M>1)M--;
for (int i = 1; i <= M+1; i++){
lsum[i+M] = msum[i+M] = rsum[i+M] = 1;
lnum[i+M] = rnum[i+M] = i<=n ? arr[i] : 0;
}
for (int len = 2, rt = M; rt >= 1; rt--) {
pushUp(rt, len);
if ((rt&(rt-1)) == 0) len <<= 1;
}
}
inline void update(int pos, int val){
lnum[pos+=M] = rnum[pos] = val;
for (int len=2, rt = pos>>1; rt; rt>>=1, len<<=1){
pushUp(rt, len);
}
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && r <= R) return msum[rt];
int ans = 0;
int m = (l + r) >> 1;
if (L <= m) ans = max(ans, query(L, R, lson));
if (m < R) ans = max(ans, query(L, R, rson));
if (rnum[lc] < lnum[rc] && L <= m && m < R){
ans = max(ans, min(m-L+1, rsum[lc])
+ min(R - m, lsum[rc]));
}
return ans;
}
inline int query(int l, int r){
return query(l, r, 1, M+1, 1);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _; scanf("%d", &_);
char op[3];
for (int n, q; _--;){
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", arr + i);
T.build(n);
for (int x, y; q--;){
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'U') T.update(x+1, y);
else printf("%d\n", T.query(x+1, y+1));
}
}
return 0;
}O HDU 3397区间合并区间赋值区间取反
注意注意注意：保证对vert操作的时候，lazy必须等于-1
lazy更新后清空vert
vert更新的时候^=1即可
lsum[][2], msum[][2], rsum[][2]
分别维护0和1的连续长度，取反的时候swap
一定要，脑子清晰了写
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 262144 + 7;
int arr[N];
// 0: 将区间[a,b]之间的数全部置为0
// 1: 将区间[a,b]之间的数全部置为1
// 2: 将区间[a,b]之间的 1->0 0->1
// 3: 求区间[a,b]之间1的个数
// 4: 求区间[a,b]之间1的最长连续长度
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M; // number of no-leaf nodes
int lsum[N][2], msum[N][2], rsum[N][2], nsum[N]; // values
int vert[N], lazy[N]; // tags
// 赋值操作，结束后记得清空vert标记
inline void setTag(const int &rt, const int &val, const int &len){
nsum[rt] = val ? len : 0;
lsum[rt][0] = msum[rt][0] = rsum[rt][0] = val ? 0 : len;
lsum[rt][1] = msum[rt][1] = rsum[rt][1] = val ? len : 0;
lazy[rt] = val;
vert[rt] = 0;
}
// 对rt节点进行取反操作，swap 0 和 1 的值
inline void vertTag(const int &rt, const int &len){
nsum[rt] = len - nsum[rt];
swap(lsum[rt][0], lsum[rt][1]);
swap(msum[rt][0], msum[rt][1]);
swap(rsum[rt][0], rsum[rt][1]);
vert[rt] ^= 1;
}
//区间合并的pushUp大体都这么写
inline void pushUp(const int &rt, const int &len){
nsum[rt] = nsum[lc] + nsum[rc];
for (int i = 0; i < 2; i++){
lsum[rt][i] = lsum[lc][i];
rsum[rt][i] = rsum[rc][i];
if (lsum[rt][i] == len>>1) lsum[rt][i] += lsum[rc][i];
if (rsum[rt][i] == len>>1) rsum[rt][i] += rsum[lc][i];
msum[rt][i] = max(msum[lc][i], msum[rc][i]);
msum[rt][i] = max(msum[rt][i], rsum[lc][i] + lsum[rc][i]);
}
}
// 优先lazy标记，但是不要干扰vert标记
// vert的时候进入vertTag必须保证lazy==-1
inline void pushDown(const int &rt, const int &len){
if (lazy[rt] != -1){
setTag(lc, lazy[rt], len>>1);
setTag(rc, lazy[rt], len>>1);
vert[lc] = vert[rc] = 0;
}
if (vert[rt]){
if (lazy[lc] != -1) setTag(lc, lazy[lc]^1, len>>1);
else vertTag(lc, len>>1);
if (lazy[rc] != -1) setTag(rc, lazy[rc]^1, len>>1);
else vertTag(rc, len>>1);
vert[rt] = 0;
}
lazy[rt] = -1;
}
inline void build(const int &n){
M=1; for(;M<n;) M<<=1; if(M>1)M--;
memset(vert, 0, sizeof vert);
memset(lazy,-1, sizeof lazy);
for (int i = 1; i <= M+1; i++){
nsum[i+M] = i<=n ? arr[i] : 0;
lsum[i+M][0] = msum[i+M][0] = rsum[i+M][0] = i<=n ?!arr[i] : 0;
lsum[i+M][1] = msum[i+M][1] = rsum[i+M][1] = i<=n ? arr[i] : 0;
}
for (int rt = M, len = 2; rt >= 1; rt--) {
pushUp(rt, len);
if ((rt&(rt-1)) == (!rt)) len <<= 1;//O(1)判断2的整数次幂,dep--
}
}
void update(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R){
if (val != -1) setTag(rt, val, r-l+1);
else { // invert
if (lazy[rt] != -1) setTag(rt, lazy[rt]^1, r-l+1);
else vertTag(rt, r-l+1);
}
return;
}
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
pushUp(rt, r-l+1);
}
int sum(int L, int R, int l, int r, int rt){
if (L <= l && r <= R) return nsum[rt];
pushDown(rt, r-l+1);
int m = (l + r) >> 1, ans = 0;
if (L <= m) ans += sum(L, R, lson);
if (m < R) ans += sum(L, R, rson);
return ans;
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && r <= R) return msum[rt][1];
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
// 区间合并的查询操作
int ans = min(m-L+1, rsum[lc][1]) + min(R - m, lsum[rc][1]);
if (L <= m) ans = max(ans, query(L, R, lson));
if (m < R) ans = max(ans, query(L, R, rson));
return ans;
}
// have relation with int main, out API
inline void setval(const int &l, const int &r, const int &val){
update(l, r, val, 1, M+1, 1);
}
inline void invert(const int &l, const int &r){
update(l, r, -1, 1, M+1, 1);
}
inline int sum(const int &l, const int &r){
return sum(l, r, 1, M+1, 1);
}
inline int query(const int &l, const int &r){ // continus
return query(l, r, 1, M+1, 1);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
int _; scanf("%d", &_);
for (int n, q; _--;){
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", arr + i);
T.build(n);
for (int op, l, r; q--;){
scanf("%d%d%d", &op, &l, &r);
l++, r++;
if (op == 0) T.setval(l, r, 0);
else if (op == 1) T.setval(l, r, 1);
else if (op == 2) T.invert(l, r);
else if (op == 3) printf("%d\n", T.sum(l, r));
else printf("%d\n", T.query(l, r));
}
}
return 0;
}这题一定程度考验代码能力，wa的可以稍微看看discuss
不过这个数据并没有给我起到什么作用，后来也不知道怎么过的
P HDU 2871内存管理 vector真是神奇
直接拿hotel的板子来改
加个vector来记录各个程序所用内存断，没有程序和程序间的合并操作
upper_bound和lower_bound有点抽风，自己手写一个
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef pair <int, int> P;
const int N = 65536 * 2 + 7;
vector <P> G;
vector <P>::iterator it;
inline void printG(){
for (int i = 0; i < G.size(); i++){
printf("\t\tG[%d] = [%d, %d]\n", i, G[i].fi, G[i].se);
}
}
int Search(int l, int r, int val){ // lower_bound
for (int mid; l < r;){
mid = (l + r) >> 1;
if (G[mid].fi <= val) l = mid + 1;
else r = mid;
}
return l;
}
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M, n;
int lsum[N], msum[N], rsum[N], lazy[N];
// for this problem
inline void build(const int &n){
this->n = n;
M=1; for(;M<n;) M<<=1; if(M>1)M--;
memset(lazy,-1, sizeof lazy);
for (int i = 1; i <= M+1; i++){
lsum[i+M] = msum[i+M] = rsum[i+M] = i<=n ? 1 : 0;
}
for (int rt = M; rt >= 1; rt--) {
lsum[rt] = msum[rt] = rsum[rt] = msum[lc] + msum[rc];
}
G.clear(); // holy, exiting STL
}
inline void pushUp(int rt, int len){
lsum[rt] = lsum[lc];
rsum[rt] = rsum[rc];
if (lsum[rt] == len>>1) lsum[rt] += lsum[rc];
if (rsum[rt] == len>>1) rsum[rt] += rsum[lc];
msum[rt] = max(msum[lc], msum[rc]);
msum[rt] = max(msum[rt], rsum[lc] + lsum[rc]);
}
inline void pushDown(int rt, int len){
if (lazy[rt] == -1) return;
lazy[lc] = lazy[rc] = lazy[rt];
lsum[lc] = msum[lc] = rsum[lc] = lazy[rt] ? 0 : len>>1;
lsum[rc] = msum[rc] = rsum[rc] = lazy[rt] ? 0 : len>>1;
lazy[rt] = -1;
}
void update(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R){
lsum[rt] = msum[rt] = rsum[rt] = val ? 0 : r-l+1;
lazy[rt] = val;
return;
}
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
pushUp(rt, r-l+1);
}
int query(int len, int l, int r, int rt){
if (l == r) return l;
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (msum[lc] >= len) return query(len, lson);
else if (rsum[lc] + lsum[rc] >= len) return m-rsum[lc]+1;
else if (msum[rc] >= len) return query(len, rson);
return 0;
}
// have relation with int main
inline void Reset(){
update(1, n, 0, 1, M+1, 1);
G.clear();
puts("Reset Now");
}
inline void New(const int &len){
if (msum[1] < len) puts("Reject New");
else {
int pos = query(len, 1, M+1, 1);
update(pos, pos+len-1, 1, 1, M+1, 1);
printf("New at %d\n", pos);
it = upper_bound(G.begin(), G.end(), P(pos, pos));
G.insert(it, P(pos, pos + len -1));
}
}
inline void Free(const int &val){
int p = Search(0, G.size(), val) - 1;
//printf(" debug: p = %d, [%d, %d]\n", p, G[p].l, G[p].r);
//printG();
if (p == -1 || G[p].se < val) puts("Reject Free");
else {
update(G[p].fi, G[p].se, 0, 1, M+1, 1);
printf("Free from %d to %d\n", G[p].fi, G[p].se);
G.erase(G.begin() + p);
//printG();
}
}
inline void Get(const int &rnk){
if (rnk > G.size()) puts("Reject Get");
else printf("Get at %d\n", G[rnk-1].fi);
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
char op[9];
for (int n, q; ~scanf("%d%d", &n, &q);){
T.build(n);
for (int x; q--;){
scanf("%s", op);
if (op[0] == 'R') T.Reset();
else {
scanf("%d", &x);
if (op[0] == 'N') T.New(x);
else if (op[0] == 'F') T.Free(x);
else T.Get(x);
}
}
puts("");
}
return 0;
}vector似乎比想象中的要快不少，这个vector的写法明显感觉不清真，
是不是用set更好些呢
Q HDU 1540 地道战 似乎都是单点操作
单点修改之后直接pushUp
查询到点然后递归向上时统计ans
for循环更方便^-^
#include <cmath>
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 65536 * 2 + 7;
stack <int> S;
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M;
int lsum[N], msum[N], rsum[N];
inline void pushUp(int rt, int len){
lsum[rt] = lsum[lc];
rsum[rt] = rsum[rc];
if (lsum[rt] == len>>1) lsum[rt] += lsum[rc];
if (rsum[rt] == len>>1) rsum[rt] += rsum[lc];
msum[rt] = max(msum[lc], msum[rc]);
msum[rt] = max(msum[rt], rsum[lc] + lsum[rc]);
}
inline void build(const int &n){
M=1; for(;M<n;) M<<=1; if(M>1)M--;
for (int i = 1; i <= M+1; i++){
lsum[i+M] = msum[i+M] = rsum[i+M] = i<=n ? 1 : 0;
}
for (int rt = M, len = 2; rt >= 1; rt--) {
pushUp(rt, len);
if ((rt&(rt-1)) == !rt) len <<= 1;
}
}
void update(int &pos, const int &val){
lsum[pos+=M] = msum[pos] = rsum[pos] = val;
for (int rt = pos>>1, len = 2; rt; rt>>=1, len <<= 1){
pushUp(rt, len);
}
}
int query(const int &pos){
int ans = msum[pos+M];
if (!ans) return 0;
bool fromR = (pos + M) & 1;
for (int rt=(pos+M)>>1, l=pos, r=pos; rt; fromR=rt&1, rt>>=1){
if (fromR){
if (lsum[rc]==ans && ans>=pos-l+1) ans += rsum[lc];
l -= (r - l + 1);
} else {
if (rsum[lc]==ans && ans>=r-pos+1) ans += lsum[rc];
r += (r - l + 1);
}
}
return ans;
}
} T;
int main(){
//freopen("in.txt", "r", stdin);
char op[7];
for (int n, q; ~scanf("%d%d", &n, &q);){
T.build(n);
for (;!S.empty();) S.pop();
for (int pos; q--;){
scanf("%s", op);
if (op[0] == 'R') {
pos = S.top(); S.pop();
T.update(pos, 1);
} else {
scanf("%d", &pos);
if (op[0] == 'Q') printf("%d\n", T.query(pos));
else {
S.push(pos);
T.update(pos, 0);
}
}
}
}
return 0;
}R CodeForces 46D Parking Lot 板子稍微改改
直接拿Hotel的板子出来改个int main就好了
做到这题的时候脑子快生锈了，把01搞反了测样例测了好久
线段树区间开n+b+f，注意op=2的时候的x操作的是第x次操作的车出来
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;
const int N = 65536 * 2 * 2 + 7;
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M;
int lsum[N], msum[N], rsum[N], lazy[N];
inline void pushUp(int rt, int len){
lsum[rt] = lsum[lc];
rsum[rt] = rsum[rc];
if (lsum[rt] == len>>1) lsum[rt] += lsum[rc];
if (rsum[rt] == len>>1) rsum[rt] += rsum[lc];
msum[rt] = max(msum[lc], msum[rc]);
msum[rt] = max(msum[rt], rsum[lc] + lsum[rc]);
}
inline void pushDown(int rt, int len){
if (lazy[rt] == -1) return;
lazy[lc] = lazy[rc] = lazy[rt];
lsum[lc] = msum[lc] = rsum[lc] = lazy[rt] ? 0 : len>>1;
lsum[rc] = msum[rc] = rsum[rc] = lazy[rt] ? 0 : len>>1;
lazy[rt] = -1;
}
inline void build(const int &n){
M=1; for(;M<n;) M<<=1; if(M>1)M--;
memset(lazy,-1, sizeof lazy);
for (int i = 1; i <= M+1; i++){
lsum[i+M] = msum[i+M] = rsum[i+M] = i<=n ? 1 : 0;
}
for (int rt = M, len = 2; rt >= 1; rt--) {
pushUp(rt, len);
if ((rt&(rt-1)) == (!rt)) len <<= 1;
}
}
void update(int L, int R, int val, int l, int r, int rt){
if (L <= l && r <= R){
lsum[rt] = msum[rt] = rsum[rt] = val ? 0 : r-l+1;
lazy[rt] = val;
return;
}
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, val, lson);
if (m < R) update(L, R, val, rson);
pushUp(rt, r-l+1);
}
int query(int len, int l, int r, int rt){
if (l == r) return l;
pushDown(rt, r-l+1);
int m = (l + r) >> 1;
if (msum[lc] >= len) return query(len, lson);
else if (rsum[lc] + lsum[rc] >= len) return m - rsum[lc] + 1;
else if (msum[rc] >= len) return query(len, rson);
return 0;
}
// have relation with int main
inline void update(const int &l, const int &r, const int &val){
update(l, r, val, 1, M+1, 1);
}
inline int query(const int &len){
return query(len, 1, M+1, 1);
}
} T;
P car[111];
int main(){
//freopen("in.txt", "r", stdin);
for (int n, b, f, q; ~scanf("%d%d%d%d", &n, &b, &f, &q);){
n += b + f;
T.build(n);
for (int op, x, pos, i = 1; i <= q; i++){
scanf("%d%d", &op, &x);
if (op == 1){ // query
if (T.msum[1] < b + x + f) puts("-1");
else {
pos = T.query(b + x + f);
car[i] = P(pos + b, pos + b + x - 1);
printf("%d\n", pos - 1);
T.update(car[i].fi, car[i].se, 1);
}
} else T.update(car[x].fi, car[x].se, 0);
}
}
return 0;
}扫描线
S HDU 1542 Atlantis矩形面积并
经典题
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 9999;
struct Seg{
double l, r, h; // height
int s; // status
Seg(){}
Seg(double x, double y, double z, int w): l(x), r(y), h(z), s(w){}
bool operator < (const Seg & b) const {return h < b.h;}
} seg[N];
double ux[N];
int X, S; // top of seg[] & ux[]
struct segTree{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M, cnt[N];
double sum[N];
inline void build(int n){
M=1; while(M<n)M<<=1; if(M>1)M--;
memset(sum, 0, sizeof sum);
memset(cnt, 0, sizeof cnt);
}
inline void pushUp(int rt, int l, int r){
if (cnt[rt]) sum[rt] = ux[r+1] - ux[l];
else sum[rt] = l==r ? 0 : sum[lc] + sum[rc];
}
void update(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
cnt[rt] += x;
pushUp(rt, l, r);
return;
}
LL m = (l + r) >> 1;
if (L <= m) update(L, R, x, lson);
if (m < R) update(L, R, x, rson);
pushUp(rt, l, r);
}
// for int main
inline void update(int l, int r, int val){
update(l, r, val, 1, M+1, 1);
}
} T;
int Search(double key, int l, int r, double ux[]){
for (; l <= r;){
int m = (l + r) >> 1;
if (ux[m] == key) return m;
if (ux[m] < key) l = m + 1;
else r = m -1;
}
return -1;
}
int main(){
//freopen("in.txt", "r", stdin);
for (int n, _ = 1; ~scanf("%d", &n) && n;){
printf("Test case #%d\n", _++);
X = S = 0;
for (int i = 1; i <= n; i++){
double l, low, r, high;
scanf("%lf%lf%lf%lf", &l, &low, &r, &high);
ux[++X] = l;
ux[++X] = r;
seg[++S] = Seg(l, r, low, 1);
seg[++S] = Seg(l, r, high, -1);
}
sort(seg + 1, seg + S+1);
sort(ux + 1, ux + X+1);
X = unique(ux + 1, ux + X +1) - ux - 1;
ux[X+1] = ux[X];
T.build(X);
double ans = 0;
for (int i = 1; i < S; i++){
int l = Search(seg[i].l, 1, X, ux);
int r = Search(seg[i].r, 1, X, ux) - 1;
T.update(l, r, seg[i].s);
ans += T.sum[1] * (seg[i+1].h - seg[i].h);
}
printf("Total explored area: %.2lf\n\n", ans);
}
return 0;
}推荐阅读