P3224 [HNOI2012]永无乡
这题太丢人了
本来想写一个 fhq 的启发式合并，但是觉得很麻烦（每次启发式合并的时候不知道怎么弄（貌似只要split根节点和它的有的儿子就行了？，当时我想的是每次取出这个小平衡树的第1大然后split这个值貌似复杂度是 log3 的？于是果断放弃） ）
然后写了一个权值线段树的启发式合并，然后丢人地调了两个多小时才发现线段树里面的 sz 数组和并查集那个 sz 用混在一起了然后交上去直接给A了怪毙了
实际利用一个 DFS 就可以两 log 做
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define ls(i) t[(i)].l
#define rs(i) t[(i)].r
using namespace std;
const int maxn=200200;
int n,m,a[maxn],rt[maxn];
int looker[maxn];
int f[maxn];
int sz[maxn],tot;
struct segment_tree{
struct tree{
int l,r,sz;
}t[maxn*32];
void ins_tree(int &i,int looker,int l,int r,int x)
{
if(!i) i=++tot;
t[i]=t[looker];
t[i].sz++;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) ins_tree(ls(i)=++tot,ls(looker),l,mid,x);
else ins_tree(rs(i)=++tot,rs(looker),mid+1,r,x);
}
int kth_tree(int i,int l,int r,int k)
{
if(k<0||!i) return -1;
if(l==r) return l;
int mid=(l+r)>>1;
if(k>t[ls(i)].sz)
{
k-=t[ls(i)].sz;
kth_tree(rs(i),mid+1,r,k);
}
else return kth_tree(ls(i),l,mid,k);
}
int merge_tree(int i,int looker,int l,int r)
{
if(!i||!looker) return i+looker;
if(l==r)
{
t[i].sz+=t[looker].sz;
return i;
}
int mid=(l+r)>>1;
ls(i)=merge_tree(ls(i),ls(looker),l,mid);
rs(i)=merge_tree(rs(i),rs(looker),mid+1,r);
t[i].sz=t[ls(i)].sz+t[rs(i)].sz;
return i;
}
}st;
int getfather(int x)
{
if(x==f[x]) return x;
return f[x]=getfather(f[x]);
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
looker[a[i]]=i;
f[i]=i;
sz[i]=1;
st.ins_tree(rt[i],rt[0],1,n,a[i]);
}
char opt;
int x,y;
for(i=1;i<=m;i++)
{
cin>>x>>y;
x=getfather(x);
y=getfather(y);
if(sz[x]<sz[y]) swap(x,y);
rt[f[x]]=st.merge_tree(rt[f[x]],rt[f[y]],1,n);
sz[f[x]]+=sz[f[y]];
f[y]=f[x];
}
cin>>m;
for(i=1;i<=m;i++)
{
cin>>opt>>x>>y;
if(opt=='B')
{
x=getfather(x);
y=getfather(y);
if(sz[x]<sz[y]) swap(x,y);
sz[f[x]]+=sz[f[y]];
rt[f[x]]=st.merge_tree(rt[f[x]],rt[f[y]],1,n);
f[y]=f[x];
}
if(opt=='Q')
{
x=getfather(x);
int ucc=st.kth_tree(rt[f[x]],1,n,y);
if(ucc!=-1) ucc=looker[ucc];
cout<<ucc<<"\n";
}
}
return 0;
}
|
P2617 Dynamic Rankings
主席树单调修改区间第 k 大
刚开始的时候听说可以用树状数组处理修改，但是依旧是想的从[l,r] 前缀和形式这种形式修改，然后光荣地9.8写完代码然后9.11才AC
然后看了下题解，说明几个原理
修改树状数组下标的位置，将x±lowbit 视为一个等价类，根据常识，不同的等价类互不干扰
对于查询，把所有的等价类并起来，可以证明这些等价类的并可以代表所有元素（参考树状数组正确性的证明）
然后开空间，离散化后线段树要开最多 log2(n) 个空间 不离散化要开log1e9×logn 的空间，后者可以被卡到480倍，前者最多256倍，所以我开的320倍做法其实是运气好没被卡。
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define ls(i) t[(i)].l
#define rs(i) t[(i)].r
#define sz(i) t[(i)].sz
using namespace std;
const int maxn=100100;
const int mmx=1e9;
int a[maxn];
int rt[maxn],tmp1[50],tmp2[50],cnt1,cnt2;
int tot;
int n,m;
struct segment_tree{
struct tree{
int l,r,sz;
}t[maxn*320];
void change_tree(int &i,int looker,int l,int r,int x,int target)
{
if(!i) i=++tot;
t[i].sz+=target;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) change_tree(ls(i),ls(looker),l,mid,x,target);
else change_tree(rs(i),rs(looker),mid+1,r,x,target);
}
int kth_tree(int *i,int *looker,int l,int r,int k)
{
int totsz=0;
int j=0;
if(l==r) return l;
for(j=1;j<=cnt1;j++) totsz+=sz(ls(i[j]));
for(j=1;j<=cnt2;j++) totsz-=sz(ls(looker[j]));
int mid=(l+r)>>1;
if(k>totsz)
{
k-=totsz;
for(j=1;j<=cnt1;j++) i[j]=rs(i[j]);
for(j=1;j<=cnt2;j++) looker[j]=rs(looker[j]);
return kth_tree(i,looker,mid+1,r,k);
}
else
{
for(j=1;j<=cnt1;j++) i[j]=ls(i[j]);
for(j=1;j<=cnt2;j++) looker[j]=ls(looker[j]);
return kth_tree(i,looker,l,mid,k);
}
}
}st;
inline int lowbit(int x)
{
return x&(-x);
}
inline void pushask_tree(int x,int &p,int *tmp)
{
p=0; while(x) tmp[++p]=rt[x],x-=lowbit(x);
}
inline void pushchg_tree(int x,int k,int p)
{
while(x<=n)
{
st.change_tree(rt[x],rt[x-1],1,mmx,k,p);
x+=lowbit(x);
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
char opt;
int l,r,x;
for(i=1;i<=n;i++)
{
cin>>a[i];
pushchg_tree(i,a[i],1);
}
for(i=1;i<=m;i++)
{
cin>>opt;
if(opt=='Q')
{
cin>>l>>r>>x;
cnt1=cnt2=0;
pushask_tree(r,cnt1,tmp1);
pushask_tree(l-1,cnt2,tmp2);
cout<<st.kth_tree(tmp1,tmp2,1,mmx,x)<<'\n';
}
if(opt=='C')
{
cin>>l>>x;
pushchg_tree(l,a[l],-1);
a[l]=x;
pushchg_tree(l,a[l],1);
}
}
return 0;
}
|
P3797 妖梦斩木棒
刚开始拿到题，网友直呼不可做
然后昏析，好像中间有没有 X 都没用，于是分析 (,) 的情况。
首先我们记录一个区间最右边出现的 ( 的位置，记做 ln
然后记录一个区间最左边出现的 ) 的位置，记做rn
然后有什么用？我们记录这两个区间合并后的答案，只需考虑左边木棒的个数+右边的个数，以及左区间最右边的和右区间最左边能不能构成一个木棒（这种情况意味着左边区间最右边是 ( ，右边区间最左边是 ) ）就行了
然而光是 ln,rn 不能记录得到答案，我们还需要最右边是不是形如 (XXXXX 的这种序列，最左边是不是形如 XXXXX) 这种序列（这个地方我用了一个很奇怪的方法，代码里面说）
然后我们就可以记录答案了
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define ls i<<1
#define rs i<<1|1
using namespace std;
const int maxn=200100;
struct tree{
int ans,ln,rn,lp,rp,sum;
}t[maxn<<2];
int n,m;
struct orztree{
inline void pushup(int i)
{
if(!t[rs].ln) t[i].ln=t[ls].ln; else t[i].ln=t[rs].ln;
if(!t[ls].rn) t[i].rn=t[rs].rn; else t[i].rn=t[ls].rn;
if(!t[rs].sum) t[i].lp=t[rs].lp; else t[i].lp=t[ls].lp;
if(!t[ls].sum) t[i].rp=t[ls].rp; else t[i].rp=t[rs].rp;
t[i].sum=t[ls].sum&t[rs].sum;
t[i].ans=t[ls].ans+t[rs].ans;
if(t[ls].lp&&t[rs].rp) t[i].ans++;
}
void build_tree(int i,int l,int r)
{
if(l==r) t[i].sum=1;
if(l==r) return ;
int mid=(l+r)>>1;
build_tree(lson);
build_tree(rson);
pushup(i);
}
void change_tree(int i,int l,int r,int x,int target)
{
if(l==r)
{
if(target==0)
{
t[i].sum=1;
t[i].ln=0;
t[i].rn=0;
t[i].lp=0;
t[i].rp=0;
}
if(target==1)
{
t[i].ln=l;
t[i].lp=1;
t[i].rn=0;
t[i].rp=0;
t[i].ans=0;
t[i].sum=0;
}
if(target==2)
{
t[i].rn=l;
t[i].rp=1;
t[i].ln=0;
t[i].lp=0;
t[i].ans=0;
t[i].sum=0;
}
return ;
}
int mid=(l+r)>>1;
if(x<=mid) change_tree(lson,x,target);
else change_tree(rson,x,target);
pushup(i);
}
int getans(int i,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
{
return t[i].ans;
}
int mid=(l+r)>>1,ans=0,looker=0;
if(x<=mid) looker++,ans+=getans(lson,x,y);
if(y>mid) looker++,ans+=getans(rson,x,y);
if(looker==2)
{
ans+=(t[ls].lp&&t[rs].rp)&(t[ls].ln>=x&&t[rs].rn<=y);
}
return ans;
}
}st;
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
int opt,l,r;
char x;
st.build_tree(1,1,n);
st.change_tree(1,1,n,1,1);
st.change_tree(1,1,n,n,2);
for(i=1;i<=n;i++)
{
cin>>opt;
if(opt==1)
{
cin>>l>>x;
if(x=='X') r=0;
else if(x=='(') r=1;
else r=2;
st.change_tree(1,1,n,l,r);
}
else
{
cin>>l>>r;
cout<<st.getans(1,1,n,l,r)<<endl;
}
}
cout<<endl;
return 0;
}
|
P4231 三步必杀
刚开始以为可以维护每个等差数列，然后时间复杂度降到 mlogm
然后偷懒用了一个 set 光荣地 T 成了暴力分
我们不维护 a 考虑维护差分数组，发现一段等差数列在差分数组上是连续的一段，但是这样我还是只会做到 mlogm
考虑维护差分数组的差分数组，此时就变成了单点修改单点查询了，考虑数据结构维护，发现就是数组的模板题。
注意一下细节，由于是维护差分的差分所以减答案麻烦了，我们直接在 a 上面减和在差分的差分上面减
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
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e7+10;
int c[maxn],cc[maxn],a[maxn];
int ans,mmx;
int n,m;
signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
int l,r,st,ed,delta;
for(i=1;i<=m;i++)
{
cin>>l>>r>>st>>ed;
delta=(ed-st)/(r-l);
if(!delta)
{
a[l]+=st;
a[r+1]-=st;
}
else
{
cc[l]+=delta;
cc[r+1]-=delta;
a[l]+=st-delta;
a[r+1]-=ed;
}
}
for(i=1;i<=n;i++)
{
c[i]+=cc[i]+c[i-1];
a[i]+=c[i]+a[i-1];
ans^=a[i];
mmx=max(a[i],mmx);
}
cout<<ans<<" "<<mmx;
return 0;
}
|
另外下面是 set 的代码
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define its set <node>::iterator
#define int long long
using namespace std;
int n,m;
struct node{
mutable int l,r,st,delta;
node(int ll=0,int rr=0,int sst=0,int ddelta=0) {l=ll,r=rr,st=sst,delta=ddelta;}
bool operator <(const node &b)
const {
return l<b.l;
}
};
int ans=0,mmx=0;
set <node> s;
its split(int pos)
{
its it=s.lower_bound(node(pos));
if(it->l==pos&&it!=s.end()) return it;
--it;
int l,r,st,delta;
l=it->l,r=it->r,st=it->st,delta=it->delta;
s.erase(it);
s.insert(node(l,pos-1,st,delta));
return s.insert(node(pos,r,st+(pos-l)*delta,delta)).first;
}
inline void pushtag(int l,int r,int st,int delta)
{
its itl,itr;
itr=split(r+1);
itl=split(l);
for(;itl!=itr;itl++)
{
itl->delta+=delta;
itl->st+=(itl->l-l)*delta+st;
}
return ;
}
inline int getxorans(int l,int r,int st,int delta)
{
register int tans=0;
for(register int i=l;i<=r;i++)
mmx=max((i-l)*delta+st,mmx),tans^=((i-l)*delta+st);
return tans;
}
signed main()
{
register int i,j;
scanf("%lld %lld",&n,&m);
s.insert(node(1,n,0,0));
int l,r,st,ed;
for(i=1;i<=m;i++)
{
scanf("%lld %lld %lld %lld",&l,&r,&st,&ed);
if(l!=r)pushtag(l,r,st,(ed-st)/(r-l));
else pushtag(l,r,st,st);
}
for(its it=s.begin();it!=s.end();it++)
{
ans^=getxorans(it->l,it->r,it->st,it->delta);
}
printf("%lld %lld",ans,mmx);
return 0;
}
|
P2584 [ZJOI2006]GameZ游戏排名系统/P4291 [HAOI2008]排名系统
妈耶怎么这么毒瘤
刚开始 set 莽上去， 没想到 50 分
然后换成 vecotr ，开 O2 70 分
于是觉得自己差不多是正解了，于是去写了一个 FHQ 结果调了一个多小时
然后发现我只会写从小到大的平衡树（这太丢人了），只好用一个极大值去剪。
然后没发现 map 的值映射错了，以为是 namespace 的锅 ，结果改完了才发祥这个问题。
不过由于是正确的做法加了个 fhq 因此过了样例就A了（
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<ctime>
#define int long long
using namespace std;
const int maxn=250250;
const int M=maxn+10;
const int L=1e9+20;
int scr[maxn],tle[maxn];
int n,tot;
map <string,int> mp;
map <int,string> name;
namespace _3m{
queue <int> q;
}
struct node{
int score,timeline;
int name;
node (int ss=0,int tt=0,int nn=0) {score=ss,timeline=tt,name=nn;}
bool operator <(const node &b)
const {
if(score==b.score) return timeline<b.timeline;
return score>b.score;
}
};
namespace fhq_treap{
int val[maxn],c[maxn][2],rnd[maxn];
int sz[maxn];
int rt;
int x,y,z,tot;
#define ls(i) c[(i)][0]
#define rs(i) c[(i)][1]
inline void pushup(int x)
{
return void(sz[(x)]=sz[ls(x)]+sz[rs(x)]+1);
}
void split(int t,int k,int &x,int &y)
{
if(!t) return void (x=y=0);
if(val[t]>k) y=t,split(ls(t),k,x,ls(t));
else x=t,split(rs(t),k,rs(t),y);
pushup(t);
}
int creat_newnode(int x)
{
val[++tot]=x;
sz[tot]=1;
rnd[tot]=rand();
return tot;
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(rnd[x]>rnd[y])
{
rs(x)=merge(rs(x),y);
pushup(x);
return x;
}
else
{
ls(y)=merge(x,ls(y));
pushup(y);
return y;
}
}
inline void delete_tree(int target)
{
split(rt,target,x,y);
split(x,target-1,x,z);
rt=merge(x,y);
return ;
}
inline void insert_tree(int target)
{
split(rt,target,x,y);
return void (rt=merge(merge(x,creat_newnode(target)),y));
}
int ask_kth(int target)
{
split(rt,target,x,y);
split(x,target-1,x,z);
int ans=sz[x]+1;
rt=merge(merge(x,z),y);
return ans;
}
int kth(int x,int target)
{
int p=x;
while(target)
{
if(sz[ls(p)]+1<target) target-=sz[ls(p)]+1,p=rs(p);
else if(sz[ls(p)]+1==target) return val[p];
else p=ls(p);
}
return val[p];
}
inline void ask_next_10(int targetsz)
{
int target=kth(rt,targetsz);
split(rt,target-1,x,y);
for(int i=1;i<=min(10ll,sz[y]);i++) _3m::q.push(kth(y,i));
rt=merge(x,y);
}
}
inline void del_tree(int x)
{
if(!x) return ;
int sr=scr[x],tl=tle[x];
fhq_treap::delete_tree(sr*M+tl);
}
inline void ins_tree(int x,int tm)
{
fhq_treap::insert_tree(x*M+tm);
}
inline void getrklist(int x)
{
fhq_treap::ask_next_10(x);
return ;
}
inline void getrk(int x)
{
int ans=fhq_treap::ask_kth(scr[x]*M+tle[x]);
cout<<ans<<endl;
}
signed main()
{
srand(time(NULL));
register int i,j;
cin>>n;
char opt;
string s;
int x;
for(i=1;i<=n;i++)
{
cin>>opt;
if(opt=='+')
{
cin>>s>>x;
x=L-x;
del_tree(mp[s]);
name[(++tot)+x*M]=s;
mp[s]=tot;
tle[tot]=tot;
scr[tot]=x;
ins_tree(x,tot);
}
if(opt=='?')
{
cin>>s;
if(isdigit(s[0]))
{
int tl=s.size();
x=0;
for(j=0;j<tl;j++) x=x*10+s[j]-'0';
getrklist(x);
while(!_3m::q.empty())
{
int looker=_3m::q.front();
cout<<name[looker]<<" ";
_3m::q.pop();
}
cout<<endl;
}
else
{
getrk(mp[s]);
}
}
}
return 0;
}
|
P3521 [POI2011]ROT-Tree Rotations
一个很重要的结论就是，已经合并了的区间 AB,BA 对 C 的逆序对贡献一样，这个就很显然可以每次都选最优，答案一定是最优的
考虑合并，实际上可以用一个线段树，复杂度 O(nlogn) 注意 int 会炸
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=500250;
int ls[maxn],rs[maxn];
int rt[maxn];
int tot,n,leafsum;
int ans,Rt;
int a[maxn];
int pre[maxn],nxt[maxn];
int ans1,ans2;
struct segment_tree{
#define ls(i) t[(i)].l
#define rs(i) t[(i)].r
int tot=0;
struct tree{
int l,r,sum;
}t[maxn*30];
inline void pushup(int i)
{
t[i].sum=t[ls(i)].sum+t[rs(i)].sum;
}
int ask_sum_tree(int &i,int l,int r,int x,int y)
{
int ans=0;
if(!i) return 0;
if(l>=x&&r<=y) return t[i].sum;
int mid=(l+r)>>1;
if(x<=mid) ans+=ask_sum_tree(ls(i),l,mid,x,y);
if(y>mid) ans+=ask_sum_tree(rs(i),mid+1,r,x,y);
return ans;
}
void change_tree(int &i,int l,int r,int x,int target)
{
if(!i) i=++tot;
t[i].sum++;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) change_tree(ls(i),l,mid,x,target);
else change_tree(rs(i),mid+1,r,x,target);
}
inline int merge_tree(int i,int looker,int l,int r)
{
if(!i||!looker) return i|looker;
ans1+=t[ls(looker)].sum*t[rs(i)].sum;
ans2+=t[ls(i)].sum*t[rs(looker)].sum;
t[i].sum+=t[looker].sum;
if(l==r) return i;
int mid=(l+r)>>1;
ls(i)=merge_tree(ls(i),ls(looker),l,mid);
rs(i)=merge_tree(rs(i),rs(looker),mid+1,r);
return i;
}
}st;
void read_tree(int &i)
{
int x;
if(!i) i=++tot;
cin>>x;
if(!x)
{
read_tree(ls[i]);
read_tree(rs[i]);
pre[i]=pre[ls[i]];
nxt[i]=nxt[rs[i]];
}
else
{
leafsum++;
a[leafsum]=x;
pre[tot]=nxt[tot]=leafsum;
st.change_tree(rt[tot],1,n,x,1);
}
return;
}
void getans(int t)
{
int l,r;
if(!t) return ;
l=ls[t],r=rs[t];
if(!l&&!r) return ;
getans(l); getans(r);
if(!r) rt[t]=st.merge_tree(rt[t],rt[l],1,n);
if(!l) rt[t]=st.merge_tree(rt[t],rt[r],1,n);
if(r&&l) ; else return ;
int mid=(pre[r]);
ans1=0,ans2=0;
rt[t]=st.merge_tree(rt[l],rt[r],1,n);
ans+=min(ans1,ans2);
}
signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
read_tree(Rt);
getans(Rt);
cout<<ans<<endl;
return 0;
}
|
P1502 窗口的星星
我真不愧是铁头大王
没sort就来尺取，调了一个多小时
把一个点看成 (w−1)∗(h−1) 矩形的左下角，然后矩形权值为1，接下来我们找到作为右上角的点的最大值即可
对横坐标尺取，对纵坐标用一颗线段树单点查最大值
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=100020;
int n,T,w,h,tot;
int a[maxn],b[maxn];
int posl,ans;
int posx[maxn],posy[maxn];
int profit[maxn];
struct que{
int l,r,a;
bool operator <(const que &b)
const {
return l<b.l;
}
}q[maxn];
struct segment_tree{
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define ls i<<1
#define rs i<<1|1
struct tree{
int mmx,add;
}t[maxn*4];
void clear_tree(int i,int l,int r)
{
t[i].mmx=t[i].add=0;
if(l==r) return ;
int mid=(l+r)>>1;
clear_tree(lson);
clear_tree(rson);
}
inline void pushdown(int i)
{
if(!t[i].add) return ;
t[ls].add+=t[i].add;
t[rs].add+=t[i].add;
t[ls].mmx+=t[i].add;
t[rs].mmx+=t[i].add;
t[i].add=0;
}
inline void pushup(int i)
{
t[i].mmx=max(t[ls].mmx,t[rs].mmx);
}
void change_tree(int i,int l,int r,int x,int y,int target)
{
if(l>=x&&r<=y)
{
t[i].add+=target;
t[i].mmx+=target;
return ;
}
pushdown(i);
int mid=(l+r)>>1;
if(x<=mid) change_tree(lson,x,y,target);
if(y>mid) change_tree(rson,x,y,target);
pushup(i);
}
}st;
signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>T;
while(T--)
{
cin>>n;
int tx,ty;
tot=0,ans=0;
memset(a,0,sizeof(a));
cin>>w>>h;
w--,h--;
for(i=1;i<=n;i++) cin>>q[i].l>>q[i].r>>q[i].a;
sort(q+1,q+n+1);
for(i=1;i<=n;i++)
{
tx=q[i].l; ty=q[i].r; profit[i]=q[i].a;
a[++tot]=ty;
posx[i]=tx;
posy[i]=ty;
a[++tot]=ty+h;
}
sort(a+1,a+tot+1);
tot=unique(a+1,a+tot+1)-a-1;
st.clear_tree(1,1,tot);
int l=1;
for(i=1;i<=n;i++)
{
int l1,l2;
l1=lower_bound(a+1,a+tot+1,posy[i])-a;
l2=lower_bound(a+1,a+tot+1,posy[i]+h)-a;
st.change_tree(1,1,tot,l1,l2,profit[i]);
while(posx[i]-posx[l]>w)
{
l1=lower_bound(a+1,a+tot+1,posy[l])-a;
l2=lower_bound(a+1,a+tot+1,posy[l]+h)-a;
st.change_tree(1,1,tot,l1,l2,-profit[l]);
l++;
}
ans=max(ans,st.t[1].mmx);
}
cout<<ans<<endl;
}
return 0;
}
|
