我是靠谱客的博主 唠叨灯泡,这篇文章主要介绍19 hdu多校 Rikka with Cake // 主席树(无build,大区间),现在分享给大家,希望可以做个参考。

http://acm.hdu.edu.cn/showproblem.php?pid=6681

题意:n*m大小的蛋糕,切k刀,每次切都是选一个不在边缘的点出发的射线。求最后分成了几块。

思路:等效为求交点个数+1。用两棵主席树维护纵向切的,枚举横向切的。(无build 动态开点,1e9大区间)

复制代码
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
#include<bits/stdc++.h> using namespace std; #define LL long long #define FI first #define SE second #define MP make_pair #define PII pair<int,int> const LL mod = 1e9+7; const int MX = 1e6+5; const int max_n =1e5+5,logn=40; int root[max_n*logn],ls[max_n*logn],rs[max_n*logn]; //下标为i的树他的左右子树的对应sum的下标 int sum[max_n*logn];//下标为i的区间(上面的区间对应进来)的数字数量 int cnt;//树的数量 void update(int l,int r,int &now,int last,int pos){ now=++cnt;//对应新开的区域 ls[now]=ls[last]; rs[now]=rs[last]; sum[now]=sum[last]+1; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) update(l,mid,ls[now],ls[last],pos); else update(mid+1,r,rs[now],rs[last],pos); } LL query(int L,int R,int l,int r,int t1,int t2){ if(l>=L&&r<=R) return 1LL*sum[t2]-sum[t1]; int mid=(l+r)>>1; LL re=0; if(mid>=L) re+=query(L,R,l,mid,ls[t1],ls[t2]); if(mid<R) re+=query(L,R,mid+1,r,rs[t1],rs[t2]); return re; } int ROOT[max_n*logn],LS[max_n*logn],RS[max_n*logn]; //下标为i的树他的左右子树的对应sum的下标 int SUM[max_n*logn];//下标为i的区间(上面的区间对应进来)的数字数量 int CNT;//树的数量 void UPDATE(int l,int r,int &now,int last,int pos){ now=++CNT;//对应新开的区域 LS[now]=LS[last]; RS[now]=RS[last]; SUM[now]=SUM[last]+1; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) UPDATE(l,mid,LS[now],LS[last],pos); else UPDATE(mid+1,r,RS[now],RS[last],pos); } LL QUERY(int L,int R,int l,int r,int t1,int t2){ if(l>=L&&r<=R) return 1LL*SUM[t2]-SUM[t1]; int mid=(l+r)>>1; LL re=0; if(mid>=L) re+=QUERY(L,R,l,mid,LS[t1],LS[t2]); if(mid<R) re+=QUERY(L,R,mid+1,r,RS[t1],RS[t2]); return re; } int inX[MX],inY[MX];string op[MX]; struct no{int x,y;}; bool operator<(const no &x,const no &y){ return x.x<y.x; } vector<no>vu,vd; vector<int>ux,dx; int main(){ int T;cin>>T;while(T--){ vu.clear(),vd.clear(),ux.clear(),dx.clear(); int n,m,k;cin>>n>>m>>k; for(int i=1;i<=k;i++) {scanf("%d%d",&inX[i],&inY[i]);cin>>op[i];} for(int i=1;i<=k;i++){ if(op[i][0]=='U') vu.push_back(no{inX[i],inY[i]}); if(op[i][0]=='D') vd.push_back(no{inX[i],inY[i]}); } sort(vu.begin(),vu.end());sort(vd.begin(),vd.end()); for(auto i:vu) ux.push_back(i.x); for(auto i:vd) dx.push_back(i.x); CNT=cnt=0; for(int i=0;i<(int)vu.size();i++){ update(1,1e9,root[i+1],root[i],vu[i].y);//now,last } for(int i=0;i<(int)vd.size();i++){ UPDATE(1,1e9,ROOT[i+1],ROOT[i],vd[i].y); } //cout<<root[0]<<root[1]<<root[2]; LL ans=0; for(int i=1;i<=k;i++){ if(op[i][0]=='L') { int rr=upper_bound(ux.begin(),ux.end(),inX[i])-ux.begin(); ans=ans+query(0,inY[i],1,1e9,root[0],root[rr]); rr=upper_bound(dx.begin(),dx.end(),inX[i])-dx.begin(); ans=ans+QUERY(inY[i],1e9,1,1e9,ROOT[0],ROOT[rr]); } if(op[i][0]=='R') { int ll=lower_bound(ux.begin(),ux.end(),inX[i])-ux.begin()+1; ans=ans+query(0,inY[i],1,1e9,root[ll-1],root[vu.size()]); ll=lower_bound(dx.begin(),dx.end(),inX[i])-dx.begin()+1; ans=ans+QUERY(inY[i],1e9,1,1e9,ROOT[ll-1],ROOT[vd.size()]); } } cout<<ans+1<<'n'; } return 0; }

 

最后

以上就是唠叨灯泡最近收集整理的关于19 hdu多校 Rikka with Cake // 主席树(无build,大区间)的全部内容,更多相关19内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(119)

评论列表共有 0 条评论

立即
投稿
返回
顶部