0x49「数据结构进阶」练习
4901 关押罪犯
分析题意可知，存在两个监狱，即两个相互对立的集合，囚犯之间的仇恨就是关系，就是图论中的带权无向边。因此采用扩展域并查集维护关系。考虑贪心原理，为了使答案尽量小，可以将所有矛盾关系从大到小排序，依次考虑每条边的情况。首先保证边权大的边的两端顶点在不同集合，若产生矛盾则意味着分配失败，当前冲突必然发生。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5; //题目数据范围有误 不是20000
const int INF=0x3f3f3f3f;
int n,m;
struct node{
int a,b,c;
bool operator<(const node &h)const{return c>h.c;}
}p[maxn];
int f[maxn<<1];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
ios::sync_with_stdio(false);
//freopen("关押罪犯.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>p[i].a>>p[i].b>>p[i].c;
sort(p+1,p+m+1);
for(int i=1;i<=n*2;i++) f[i]=i;
for(int i=1;i<=m;i++){
int x=p[i].a,y=p[i].b;
if(find(x)==find(y)){ //少写find(x+n)==find(y+n)没事
cout<<p[i].c;
return 0;
}
f[find(x)]=find(y+n); //必须两条都要有
f[find(y)]=find(x+n); //合并时一侧为1~n的节点 另一侧为n+1~2n的节点
}
cout<<0;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1417 True Liars
分析题意可知，说真话的人和说假话的人是两个对立的集合，因此考虑用扩展域/边带权并查集维护关系。具体到实现上，我们发现，如果回答为yes，那么两个人要么都说谎，要么都说真话。如果回答为no，那么必然一人说真话，一人说假话。处理完所有关系后，我们的到的图论模型是若干个联通块（假设有m个联通块，第i个联通块属于说真话集合的有a[i][0]个人，说假话集合的有a[i][1]个人）。这时考虑题目中的问题，要求判断能否区分联通块使得一部分联通块共有p个节点，剩下的联通块共有q个节点。这等价于求在m个联通块中选择若干个联通块，使得这些联通块中共有p个人的方案数。若方案数是1，那么说明存在唯一的可行方案。这就是01背包。当然，本题在实现时，我无法压缩掉背包的第一维，暂时原因不明。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
拓展域并查集
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=600+5;
const int INF=0x3f3f3f3f;
int n,p1,p2,u,v,f[maxn*2],d[maxn][maxn],pre[maxn][maxn],a[maxn][2],used[maxn*2],val[maxn*2];
vector<int>b[maxn][2],ans;
string s;
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
ios::sync_with_stdio(false);
//freopen("True Liars.in","r",stdin);
// freopen("True Liars.out","w",stdout);
while(cin>>n>>p1>>p2) {
if(n==0&&p1==0&&p2==0) break;
memset(d,0,sizeof(d));
memset(pre,0,sizeof(pre));
memset(used,0,sizeof(used));
memset(a,0,sizeof(a));
for(int i=1;i<=600;i++) b[i][0].clear(),b[i][1].clear();
ans.clear();
d[0][0]=1; //背包第一维不能省略 原因未知
for(int i=1; i<=2*(p1+p2); i++) f[i]=i;
for(int i=1; i<=n; i++) {
cin>>u>>v>>s;
int u1=find(u),u2=find(u+p1+p2),v1=find(v),v2=find(v+p1+p2); //注意这里要先全find出来再合并
//不能写成u=find(u) 然后f[u]=v;f[u+p1+p2]=v+p1+p2 因为 u+p1+p2没有find
if(s=="yes") {
f[u1]=v1;
f[u2]=v2;
}
if(s=="no") {
f[u1]=v2;
f[v1]=u2;
}
}
int cnt=0;
for(int i=1; i<=(p1+p2); i++){
if(used[i]) continue;
cnt++;
int temp=find(i);
for(int j=1;j<=(p1+p2);j++){
if(temp==find(j)){
used[j]=1;
a[cnt][0]++;
b[cnt][0].push_back(j);
}
if(temp==find(j+p1+p2)){
used[j]=1;
a[cnt][1]++;
b[cnt][1].push_back(j);
}
}
}
// D(cnt);E;
/*
for(int i=1; i<=cnt; i++) {
for(int j=0; j<=1; j++) {
cout<<a[i][j]<<" ";
}
cout<<endl;
}
*/
for(int i=1; i<=cnt; i++) {
if(a[i][1]==0&&a[i][0]==0) continue;
for(int j=p1; j>=0; j--) {
if(j>=a[i][0]&&d[i-1][j-a[i][0]]) {
d[i][j]+=d[i-1][j-a[i][0]];
pre[i][j]=j-a[i][0];
}
if(j>=a[i][1]&&d[i-1][j-a[i][1]]) {
d[i][j]+=d[i-1][j-a[i][1]];
pre[i][j]=j-a[i][1];
}
}
}
// cout<<d[p1]<<endl;
if(d[cnt][p1]!=1){
cout<<"no"<<endl;
continue;
}
int t=p1;
for(int i=cnt;i>=1;i--){
if(a[i][1]==0&&a[i][0]==0) continue;
int temp=t-pre[i][t];
if(temp==a[i][0]){
for(int j=0;j<a[i][0];j++) ans.push_back(b[i][0][j]);
}
else{
for(int j=0;j<a[i][1];j++) ans.push_back(b[i][1][j]);
}
t=pre[i][t];
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<endl;
}
cout<<"end"<<endl;
}
return 0;
}
#endif
POJ3667 Hotel
区间问题，试图用线段树求解。考虑一个区间的状态（即区间标记），有三种，全空，全满，其他情况。我们用一个mark表示这三种状态，对应的mark取值分别为0,1,-1。
接下来考虑一个区间中可能产生答案的可能情况，有三种，空区间紧挨左边界，空区间在中间，空区间紧挨右边界。为了方便我们表示答案和生成答案，我们给线段树对应区间节点设置如下几个信息：l,r,mark,lsum,rsum,dat。l,r表示区间左右端点，mark表示区间状态，lsum,rsum表示仅靠区间左侧/右侧的最长空区间，dat表示整个区间的最长空区间。
其中mark的更新方式类似于线段树中的延迟标记，每次query和change的时候向下传递标记。
if(tr[rt].mark!=-1){
tr[rt<<1].mark=tr[rt<<1|1].mark=tr[rt].mark;
tr[rt].mark=-1;
tr[rt<<1].update();
tr[rt<<1|1].update();
}
lsum,rsum,dat的计算则互相推导而出
tr[rt].dat=max(tr[rt<<1].dat,max(tr[rt<<1].rsum+tr[rt<<1|1].lsum,tr[rt<<1|1].dat));
tr[rt].lsum=tr[rt<<1].lsum,tr[rt].rsum=tr[rt<<1|1].rsum;
if(tr[rt<<1].dat==tr[rt<<1].r-tr[rt<<1].l+1) tr[rt].lsum+=tr[rt<<1|1].lsum;
if(tr[rt<<1|1].dat==tr[rt<<1|1].r-tr[rt<<1|1].l+1) tr[rt].rsum+=tr[rt<<1].rsum;
完整代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://www.cnblogs.com/scau20110726/archive/2013/05/07/3065418.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
struct SegmentTree{
int l,r,mark,lsum,rsum,dat;
//mark=0 区间全空 mark=1区间全满 mark=-1子区间未更新（区间未全满的状态难以计算 且会被子问题组成 所以不标记）
void update(){
lsum=rsum=dat=mark?0:r-l+1;
}
}tr[maxn<<2];
int n,m;
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r,tr[rt].mark=0,tr[rt].lsum=tr[rt].rsum=tr[rt].dat=r-l+1;
if(l==r) return;
int mid=l+r>>1;
build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}
int query(int rt,int x){
if(tr[rt].l==tr[rt].r&&x==1) return tr[rt].l;
if(tr[rt].mark!=-1){
tr[rt<<1].mark=tr[rt<<1|1].mark=tr[rt].mark;
tr[rt].mark=-1;
tr[rt<<1].update();
tr[rt<<1|1].update();
}
if(tr[rt<<1].dat>=x) return query(rt<<1,x);
if(tr[rt<<1].rsum+tr[rt<<1|1].lsum>=x) return tr[rt<<1].r-tr[rt<<1].rsum+1;
if(tr[rt<<1|1].dat>=x) return query(rt<<1|1,x);
return 0;
}
void change(int rt,int l,int r,int v){
if(tr[rt].l>=l&&tr[rt].r<=r){
tr[rt].mark=v;
tr[rt].update();
return;
}
if(tr[rt].mark!=-1){
tr[rt<<1].mark=tr[rt<<1|1].mark=tr[rt].mark;
tr[rt].mark=-1;
tr[rt<<1].update();
tr[rt<<1|1].update();
}
int mid=tr[rt].l+tr[rt].r>>1;
/*
if(r<=mid) change(rt<<1,l,r,v);
else if(l>mid) change(rt<<1|1,l,r,v);
else{
change(rt<<1,l,mid,v);
change(rt<<1|1,mid+1,r,v);
}
*/
if(l<=mid) change(rt<<1,l,r,v);
if(r>mid) change(rt<<1|1,l,r,v);
tr[rt].dat=max(tr[rt<<1].dat,max(tr[rt<<1].rsum+tr[rt<<1|1].lsum,tr[rt<<1|1].dat));
tr[rt].lsum=tr[rt<<1].lsum,tr[rt].rsum=tr[rt<<1|1].rsum;
if(tr[rt<<1].dat==tr[rt<<1].r-tr[rt<<1].l+1) tr[rt].lsum+=tr[rt<<1|1].lsum;
if(tr[rt<<1|1].dat==tr[rt<<1|1].r-tr[rt<<1|1].l+1) tr[rt].rsum+=tr[rt<<1].rsum;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Hotel.in","r",stdin);
cin>>n>>m;
build(1,1,n);
int op,x,d;
while(m--){
cin>>op>>x;
if(op==1){
int ans=query(1,x);
cout<<ans<<endl;
if(ans) change(1,ans,ans+x-1,1);
}
else{
cin>>d;
change(1,x,x+d-1,0);
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1177 Picture
有三种方法可行，法一法二参见这个博客
http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018687.html
https://www.cnblogs.com/scau20110726/archive/2013/04/13/3018702.html
第三种方法，只计算周长的一半，然后将答案乘2就是结果。具体实现中，用cx和cy数组记录每一段上的扫描线被覆盖的次数，若次数为0则表示到达了右边界/上边界，并记入答案。
但是这个博客里头的代码并不能ac本题，原因在于若出现矩形的边重叠，则会产生重复计数，这就需要所有竖线/横线在排序的过程中保证靠右/靠上的矩形的左/下边界，在排序后处于靠左/靠下的矩形的右/上边界的前面。stl中的sort函数无法实现，需要使用qsort函数计算。原因暂时不明。
方法三代码如下
/*
必须要用qsort 用sort会错误 排序方式不一样
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
int n,numx=0,numy=0,ans=0,cx[maxn],cy[maxn];
int rawx[maxn],rawy[maxn];
struct node {
int p,st,ed,f;
/*
bool operator<(const node &h)const {
return p<h.p;
}
*/
} linex[maxn],liney[maxn];//x:横线 y:竖线
int cmp(const void *a,const void *b){
return ((node *)a)->p-((node *)b)->p;
}
//int lshx[maxn],lshy[maxn];
int valx(int y) {
return lower_bound(rawx+1,rawx+numx+1,y)-rawx;
}
int valy(int y){
return lower_bound(rawy+1,rawy+numy+1,y)-rawy;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Picture.in","r",stdin);
cin>>n;
int X1,X2,Y1,Y2;
for(int i=1;i<=n;i++){
cin>>X1>>Y1>>X2>>Y2;
linex[2*i-1].p=Y1,linex[2*i-1].st=X1,linex[2*i-1].ed=X2,linex[2*i-1].f=1;
linex[2*i].p=Y2,linex[2*i].st=X1,linex[2*i].ed=X2,linex[2*i].f=-1;
liney[2*i-1].p=X1,liney[2*i-1].st=Y1,liney[2*i-1].ed=Y2,liney[2*i-1].f=1;
liney[2*i].p=X2,liney[2*i].st=Y1,liney[2*i].ed=Y2,liney[2*i].f=-1;
rawx[++numx]=X1,rawx[++numx]=X2;
rawy[++numy]=Y1,rawy[++numy]=Y2;
}
sort(rawx+1,rawx+2*n+1);
numx=unique(rawx+1,rawx+numx+1)-rawx-1;
sort(rawy+1,rawy+2*n+1);
numy=unique(rawy+1,rawy+numy+1)-rawy-1;
/*
for(int i=1;i<=2*n;i++){
lshy[valy(liney[i].st)]=lshy[valy(liney[i].ed)]=1;
}
*/
qsort(linex+1,2*n,sizeof(linex[0]),cmp);
qsort(liney+1,2*n,sizeof(liney[0]),cmp);
/*
for(int i=1;i<=2*n;i++){
cout<<"liney[i].st:"<<liney[i].st<<" liney[i].ed:"<<liney[i].ed<<endl;
}
*/
/*
for(int i=1;i<=numy;i++){
if(lshy[i]){
lshy[i]=i;
}
}
*/
/*
for(int i=1;i<=2*n;i++){
cout<<"liney[i].st:"<<liney[i].st<<" liney[i].ed:"<<liney[i].ed<<endl;
liney[i].st=lshy[valy(liney[i].st)];
liney[i].ed=lshy[valy(liney[i].ed)];
cout<<"liney[i].st:"<<liney[i].st<<" liney[i].ed:"<<liney[i].ed<<endl;
}
*/
for(int i=1;i<=2*n;i++){
for(int j=valx(linex[i].st);j<valx(linex[i].ed);j++){
cx[j]+=linex[i].f;
if(cx[j]==0){
//cout<<rawx[j+1]-rawx[j]<<" ";
ans+=rawx[j+1]-rawx[j];
}
}
}
for(int i=1;i<=2*n;i++){
// for(int j=liney[i].st;j<liney[i].ed;j++){
for(int j=valy(liney[i].st);j<valy(liney[i].ed);j++){
cy[j]+=liney[i].f;
if(cy[j]==0){
//cout<<rawy[j+1]-rawy[j]<<" ";
ans+=rawy[j+1]-rawy[j];
}
}
}
cout<<ans*2;
return 0;
}
4907 作诗
考虑类似“蒲公英”的做法，预处理出任意两个块之间每种文字的出现次数（第i块到第j块的答案记为f[i][j]），再在回答询问的时候额外朴素计算两端不完整的块的贡献即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
由于空间限制 所以原本用cnt[i][j][k]表示 第j块到第k块中种类i的出现次数会爆空间
但由于可以前缀和相减
所以 cnt[i][j]表示前j块中种类i的出现次数即可 每次询问相减就行
sum[i]表示目前种类i出现的次数
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n,c,m,num,sz,blo[maxn],a[maxn],cnt[320][maxn],f[320][320],ans=0,sum[maxn],l[320],r[320],vis[maxn],t=0;
//由于会有多次询问 但每次最多改变O(根号n)个v中的元素 所以用t来表示这次访问
void pre(){
num=int(sqrt(n));
sz=n/num;
for(int i=1;i<=n;i++) blo[i]=(i-1)/num+1;
for(int i=1;i<=num;i++) l[i]=(i-1)*sz+1,r[i]=i*sz;//l[i],r[i]数组记录第i个块的左右端点
if(r[num]!=n) l[num+1]=r[num]+1,r[++num]=n;
for(int i=1;i<=num;i++){
for(int j=1;j<=c;j++) cnt[i][j]=cnt[i-1][j];
for(int j=l[i];j<=r[i];j++) cnt[i][a[j]]++;
}
for(int i=1;i<=num;i++){
int temp=0;
memset(sum,0,sizeof(sum));
for(int j=i;j<=num;j++){
for(int k=l[j];k<=r[j];k++){
sum[a[k]]++;
if((sum[a[k]]&1)==0) temp++; //出现超过1次算
else if(sum[a[k]]>1) temp--; //出现一次不算 出现超过1次且为奇数次要-- 抵消偶数次的计算
}
f[i][j]=temp;
}
}
}
int solve(int x,int y){
int L=blo[x],R=blo[y];//blo[i]表示第i个元素所在块的编号
int ans=f[L][R];
for(int i=l[L];i<x;i++){
if(vis[a[i]]<t) vis[a[i]]=t,sum[a[i]]=cnt[R][a[i]]-cnt[L-1][a[i]];
sum[a[i]]--;
if(sum[a[i]]&1) ans--;//现在是奇数 说明曾是偶数
else if(sum[a[i]]>1) ans++; //现在是次数超过1次的偶数 说明曾是奇数
}
for(int i=y+1;i<=r[R];i++){
if(vis[a[i]]<t) vis[a[i]]=t,sum[a[i]]=cnt[R][a[i]]-cnt[L-1][a[i]];
sum[a[i]]--;
if(sum[a[i]]&1) ans--;//现在是奇数 说明曾是偶数
else if(sum[a[i]]>1) ans++; //现在是次数超过1次的偶数 说明曾是奇数
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
freopen("作诗.in","r",stdin);
cin>>n>>c>>m;
for(int i=1;i<=n;i++) cin>>a[i];
pre();
while(m--){
t++;
int L,R;
cin>>L>>R;
L=(L+ans)%n+1,R=(R+ans)%n+1;
if(L>R) swap(L,R);
ans=solve(L,R);
cout<<ans<<endl;
}
return 0;
}
#endif
4908 Race
树上路径统计问题，使用点分治算法，由于数据中可能存在链状数据，所以每次以子树重心为根进行点分治。
和「数据结构进阶」例题中的tree不同，由于不是计数问题，而是取最值问题，所以不能直接用容斥的方式统计。
但是可以用method_2的方式用ans数组记录可行情况，依次扫描求解，这样就可以使用容斥原理了 。
两种方式的代码如下（ps：method_2是容斥原理，method_3则额外维护了每个点所在的子树根节点，目前method_2状态为AC，而method_3状态为95分，原因未知）
#define method_3
#ifdef method_2
/*
容斥原理做法
ac
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 200010;
struct node {
int to,next,cost;
} e[maxn*2];
struct data {
int l,e;
} dis[maxn];
int n,m,K,tot,head[maxn],size[maxn],sz,total,vis[maxn],root,p,ans[maxn*2];
void insert(int u, int v, int w) {
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
e[tot].cost=w;
}
void getroot(int u, int f) {
int mx=0;
size[u]=1;
for (int i=head[u],v; i; i=e[i].next) {
if (vis[v=e[i].to] || v==f) continue;
getroot(v,u);
size[u]+=size[v];
mx=max(mx,size[v]);
}
mx=max(mx,total-size[u]);
if (mx<sz) sz=mx,root=u;
}
void getdis(int u, int f, int len, int num) {
dis[++p].l=len;
dis[p].e=num;
for (int i=head[u],v; i; i=e[i].next) {
if (vis[v=e[i].to] || v==f) continue;
getdis(v,u,len+e[i].cost,num+1);
}
}
bool cmp(data a, data b) {
if (a.l==b.l) return a.e<b.e;
return a.l<b.l; /////
}
void count(int u, int len, int num, int f) {
p=0;
getdis(u,0,len,num); //这里要将len和num传下去。。
int l=1,r=p;
sort(dis+1,dis+1+p,cmp);
while (l<=r) { //注意这里要用<=，WA了几发
while (l<r && dis[l].l+dis[r].l>K) r--;
for (int k=r; dis[l].l+dis[k].l==K; k--) ans[dis[l].e+dis[k].e]+=f;
l++;
}
}
void work(int u) {
total=size[u]?size[u]:n;
sz=INF;
getroot(u,0);
u=root;
vis[u]=1;
count(u,0,0,1);
for (int i=head[u],v; i; i=e[i].next) {
if (vis[v=e[i].to]) continue;
count(v,e[i].cost,1,-1);
work(v);
}
}
int main() {
scanf("%d%d", &n, &K);
for (int i=1,u,v,w; i<n; i++) scanf("%d%d%d", &u, &v, &w),u++,v++,insert(u,v,w),insert(v,u,w);
work(1);
for (int i=1; i<n; i++) if (ans[i]) {
printf("%d\n", i);
return 0;
}
puts("-1");
return 0;
}
#endif
#ifdef method_3
/*
维护每个点所在子树的做法
有一个点wa 九十五分
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200000+5;
const int INF=0x3f3f3f3f;
int n,k,head[maxn],root,mxson[maxn],s[maxn],cnt=0,ans=INF,mins,tot=0,vis[maxn];
struct node {
int from,to,v;
} edge[maxn<<1];
struct node1{
int d,c,b;
bool operator<(const node1 &h)const{return d<h.d||(d==h.d&&c<h.c);}
}dis[maxn];
void add(int from,int to,int v) {
edge[++cnt].to=to,edge[cnt].v=v,edge[cnt].from=head[from],head[from]=cnt;
}
void getdis(int x,int len,int num,int belong) {
vis[x]=1; //由于点分治之后 x节点的所有父系节点都统计结束了 所以需要用vis而不用fa
dis[++tot].d=len,dis[tot].c=num,dis[tot].b=belong;
for(int i=head[x]; i; i=edge[i].from) {
int y=edge[i].to,v=edge[i].v;
if(vis[y]) continue;
getdis(y,len+v,num+1,belong);
}
vis[x]=0;
}
void getroot(int S,int x) { //求以x节点为根，大小为S的子树，存在全局变量root中
s[x]=1,vis[x]=1;
int max_part=0;
for(int i=head[x]; i; i=edge[i].from) {
int y=edge[i].to;
if(vis[y]) continue;
getroot(S,y);
s[x]+=s[y];
max_part=max(max_part,s[y]);
}
max_part=max(max_part,S-s[x]);
if(max_part<mins) {
mins=max_part;
root=x;
}
vis[x]=0;
}
void divide(int S,int x) { //以x节点为根，大小为S的子树上经过根节点的路径统计
mins=S;
getroot(S,x);
tot=0;
vis[root]=1;
dis[++tot].d=0,dis[tot].b=root,dis[tot].c=0;
for(int i=head[root]; i; i=edge[i].from) {
int y=edge[i].to,v=edge[i].v;
if(vis[y]) continue;
getdis(y,v,1,y);
}
sort(dis+1,dis+tot+1);
/*
for(int i=1;i<=tot;i++){
cout<<dis[i].b<<" "<<dis[i].c<<" "<<dis[i].d<<endl;
}
cout<<endl<<endl;
*/
int L=1,R=tot;
while(L<=R) {
while(L<R&&dis[L].d+dis[R].d>k) R--;
while(dis[L].d+dis[R].d==k&&L<R) {
if(dis[L].b!=dis[R].b) ans=min(ans,dis[L].c+dis[R].c);
R--;
}
L++;
}
int now=root;
//由于root是全局变量 所以会在divide递归的过程中不断变化 因此这里要用now变量暂时保存这一层的root
for(int i=head[now]; i; i=edge[i].from) {
int y=edge[i].to;
if(vis[y]) continue;
divide(s[y],y);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Race.in","r",stdin);
cin>>n>>k;
int from,to,v;
for(int i=1; i<=n-1; i++) {
cin>>from>>to>>v;
add(from,to,v),add(to,from,v);
}
ans=n;
divide(n,0);
if(ans==n) cout<<-1;
else cout<<ans;
return 0;
}
#endif
4909 营业额统计
平衡树维护前驱后继的模板题，手写平衡树或者用set都能AC。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=32767+5;
const int INF=0x3f3f3f3f;
int n,ans=0,tot=0,root;
struct node {
int l,r,dat,val;
} a[maxn];
int New(int val) {
a[++tot].val=val,a[tot].dat=rand();
return tot;
}
void Build() {
a[1].r=2,root=1;
New(-INF*2),New(INF*2);
}
void zig(int &p) {
int q=a[p].l;
a[p].l=a[q].r,a[q].r=p;
p=q;
// Update(a[p].r),Update(p);
}
void zag(int &p) {
int q=a[p].r;
a[p].r=a[q].l,a[q].l=p;
p=q;
// Update(a[p].l),Update(p);
}
void insert(int &p,int val) {
if(p==0) {
p=New(val);
return;
}
if(val<=a[p].val) {
insert(a[p].l,val);
if(a[p].dat<a[a[p].l].dat) zig(p);
} else {
insert(a[p].r,val);
if(a[p].dat<a[a[p].r].dat) zag(p);
}
}
int GetPre(int val) {
int p=root,ans=-INF;
while(p) {
if(val==a[p].val)return a[p].val;
if(val>a[p].val) ans=max(ans,a[p].val),p=a[p].r;
else p=a[p].l;
}
return ans;
}
int GetNext(int val) {
int p=root,ans=INF;
while(p) {
if(val==a[p].val)return a[p].val;
if(val<a[p].val) ans=min(ans,a[p].val),p=a[p].l;
else p=a[p].r;
}
return ans;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("营业额统计.in","r",stdin);
cin>>n;
int x;
Build();
for(int i=1; i<=n; i++) {
if(scanf("%d",&x)==EOF)x=0; //这题数据有问题 有一个点数据不全 要加上这句话
int temp1=GetPre(x),temp2=GetNext(x);
if(i==1) ans+=abs(x);
else ans+=min(x-temp1,temp2-x);
insert(root,x);
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=32767+5;
const int INF=0x3f3f3f3f;
int n,ans=0;
multiset<int>s;
multiset<int>::iterator it;
int main() {
ios::sync_with_stdio(false);
//freopen("营业额统计.in","r",stdin);
cin>>n;
int x;
for(int i=1; i<=n; i++) {
cin>>x;
s.insert(x);
int temp=INF;
if(i==1) {ans+=abs(x);continue;}
it=s.find(x);
if(it!=s.begin()){
--it;
temp=min(temp,x-(*it));
it++;
}
it++;
if(it!=s.end()){
temp=min(temp,(*it)-x);
}
ans+=temp;
}
cout<<ans;
return 0;
}
#endif
POJ3580 SuperMemo
这种虐区间的题目往往是Splay的菜，然而我只会treap，所以我学学用fhq_treap即无旋treap/可持久化treap来做。然而，我目前还没有看懂fhq_treap，因此这道题暂时坑着。
4911 Mokia
cdq分治裸题，注意如下两点：
1 用结构体中的pos变量来记录操作的编号，做到询问的顺序输出。
2 树状数组维护一维坐标，所以树状数组的所有操作范围都是这一维下标的坐标范围。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=160000+40000+5;
const int maxp=2000000+5;
const int INF=0x3f3f3f3f;
int s,w,opt,n=0,ans[maxn],c[maxp];//树状数组维护一维坐标，所以树状数组的所有操作范围都是这一维下标的坐标范围。所以是maxp而不是maxn
struct node{
int op,x,y,val,sum,pos;
bool operator<(const node &h)const{return x<h.x||(x==h.x&&op<h.op);}
}a[maxn],t[maxn];
void add(int x,int v){
for(int i=x;i<=w;i+=i&-i) c[i]+=v; //注意i的上界是w 不是n
}
int ask(int x){
int temp=0;
for(int i=x;i>=1;i-=i&-i) temp+=c[i];
return temp;
}
void cdq(int l,int r){
if(l>=r) return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
int p=0;
for(int i=l;i<=r;i++){
if((a[i].op==1&&i<=mid)||(a[i].op==2&&i>mid)){
t[++p]=a[i],t[p].pos=i;
}
}
sort(t+1,t+p+1);
for(int i=1;i<=p;i++){
if(t[i].op==1) add(t[i].y,t[i].val);
else a[t[i].pos].sum+=ask(t[i].y);
}
for(int i=1;i<=p;i++){
if(t[i].op==1){
add(t[i].y,-t[i].val);
}
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("Mokia.in","r",stdin);
cin>>s>>w;
int x,y,x2,y2,temp;
while(cin>>opt&&opt!=3){
if(opt==1){
cin>>x>>y>>temp;
a[++n].op=1,a[n].x=x,a[n].y=y,a[n].val=temp;
}
else{
cin>>x>>y>>x2>>y2;
ans[++n]=abs(x2-x+1)*abs(y2-y+1)*s;
a[n].op=2,a[n].x=x-1,a[n].y=y-1,a[n].sum=0;
a[++n].op=2,a[n].x=x-1,a[n].y=y2,a[n].sum=0;
a[++n].op=2,a[n].x=x2,a[n].y=y-1,a[n].sum=0;
a[++n].op=2,a[n].x=x2,a[n].y=y2,a[n].sum=0;
}
}
cdq(1,n);
for(int i=1;i<=n;i++){
if(a[i].op==2){
int temp=ans[i];
temp+=a[i].sum;
temp-=a[++i].sum;
temp-=a[++i].sum;
temp+=a[++i].sum;
cout<<temp<<endl;
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
4912 Meteors
分析题意可知，需要求解每个国家最少需要接受多少轮陨石雨。如果只求一个国家，可以考虑使用二分答案的做法。现在由于求解的国家数较多，所以考虑使用基于值域的整体二分。
与此同时，为了避免区间修改导致的复杂度退化，我们利用差分序列将区间修改改为单点修改，并用树状数组维护。
具体实现上，用如下代码可以做到处理区间的顺时针和逆时针问题。
void change(int i,int num){
if(a[i].l>a[i].r) add(1,a[i].w*num);
add(a[i].l,a[i].w*num);
add(a[i].r+1,-a[i].w*num);
}
完整代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,ll>pii; //first记录答案的顺序
const int maxn=3e5+5;
const ll INF=0x3f3f3f3f3f3f3fll;
ll c[maxn];
int n,m,k,temp,ans[maxn];
pii q[maxn],lq[maxn],rq[maxn];
vector<int>e[maxn];
struct node{
ll l,r,w;
}a[maxn];
void add(int x,ll v){
for(int i=x;i<=m;i+=i&-i) c[i]+=v;
}
ll ask(int x){
ll sum=0;
for(int i=x;i>=1;i-=i&-i) sum+=c[i];
return sum;
}
void change(int i,int num){
if(a[i].l>a[i].r) add(1,a[i].w*num);
add(a[i].l,a[i].w*num);
add(a[i].r+1,-a[i].w*num);
}
void solve(int lval,int rval,int st,int ed){
if(st>ed) return;
if(lval==rval){
for(int i=st;i<=ed;i++){
ans[q[i].first]=lval;
// cout<<i<<" "<<q[i].first<<endl; 两个不一样
}
return;
}
int mid=lval+rval>>1,lt=0,rt=0;
for(int i=lval;i<=mid;i++) change(i,1); //由于所有操作都是同一个类型的（区间修改），所以这里的做法比整体二分的模板有所简化
for(int i=st;i<=ed;i++){
ll tot=0;
for(int j=0;j<e[q[i].first].size();j++){
tot+=ask(e[q[i].first][j]);
if(tot>q[i].second) break;
}
if(tot>=q[i].second) lq[++lt]=q[i];
else q[i].second-=tot,rq[++rt]=q[i];
}
for(int i=lval;i<=mid;i++) change(i,-1);
for(int i=1;i<=lt;i++) q[i+st-1]=lq[i];
for(int i=1;i<=rt;i++) q[i+lt+st-1]=rq[i];
solve(lval,mid,st,st+lt-1);
solve(mid+1,rval,st+lt,ed);
}
int main() {
ios::sync_with_stdio(false);
freopen("Meteors.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>temp,e[temp].push_back(i);
for(int i=1;i<=n;i++) q[i].first=i,cin>>q[i].second;
cin>>k;
for(int i=1;i<=k;i++) cin>>a[i].l>>a[i].r>>a[i].w;
a[++k].l=1,a[k].r=m,a[k].w=INF;
solve(1,k,1,n);
for(int i=1;i<=n;i++){
if(ans[i]==k) cout<<"NIE"<<endl;
else cout<<ans[i]<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
4913 Fotile模拟赛L
根据区间异或和的特性，将区间异或转化为异或前缀和后的两个端点异或的最大值。直接对于每个询问枚举端点求解，时间复杂度为。
考虑优化，假设左右端点没有范围限制，我们可以将每个数拆分二进制，从高位到低位插入一棵可持久化trie。然后枚举右端点r，在可持久化trie中从高位到低位，贪心查找每一位与a[r]（此时a数组是异或前缀和数组）相反的指针，如果存在则这一位（第i位）就对答案产生了1<<i的贡献。
若存在左右端点的限制，就需要对每个trie上的节点记录一个变量rpos表示这个节点最靠右的节点编号。每次在trie上贪心查找的时候，只考虑rpos>=l的情况即可。
这样做的时间复杂度。
考虑继续优化，我们可以分块预处理答案，设b[i][j]表示第i块中，第i*l+1到j的a数组的异或和的最大值，其中l为块数。
最终时间复杂度。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=12000+5;
const int maxm=6000+5;
const int maxlogn=32+5;
const int maxsqrtn=120+5;
const int INF=0x3f3f3f3f;
int trie[maxn*maxlogn][2],rpos[maxn*maxlogn]={-1},h[maxn],n,m,tot=0,a[maxn],x,y,ans=0,b[maxsqrtn][maxn];
//注意rpos要初始化为-1
void insert(int last,int now,int k){
int p;
h[k]=p=++tot,rpos[p]=k; //h数组记录每个历史时期trie的根节点
for(int i=30;i>=0;i--){
int j=(now>>i)&1;
trie[p][j^1]=trie[last][j^1]; //复制原先的树
trie[p][j]=++tot;
p=tot,rpos[p]=k;
last=trie[last][j];
}
}
int ask(int l,int r,int x){
int p=h[r],ans=0;
for(int i=30;i>=0;i--){
int j=((x>>i)&1)^1;
if(rpos[trie[p][j]]>=l) ans|=1<<i;
else j^=1;
p=trie[p][j];
}
return ans;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Fotile模拟赛L.in","r",stdin);
// freopen("Fotile模拟赛L.out","w",stdout);
cin>>n>>m;
int t=(int)sqrt(n);
int l=n/t+(n%t!=0);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]^=a[i-1];
insert(h[0],a[0],0);
for(int i=1;i<=n;i++) insert(h[i-1],a[i],i);
for(int i=0;i<t;i++){
for(int j=i*l+1;j<=n;j++){
b[i][j]=max(b[i][j-1],ask(i*l,j-1,a[j]));
//b[i][j]表示第i块中，第i*l+1到j的a数组的异或和的最大值
//注意由于转化为了异或前缀和 所以[l,r]的最大异或和等价于[l-1,r]中找两个异或前缀和的点异或最大
//因此这里是i*l而不是i*l+1
}
}
int i; //见了鬼了 这个i要定义在这里 定义在循环里会慢20倍 所以 有的编译器根本不允许在for里定义
while(m--){
scanf("%d%d",&x,&y);
//l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 )
x=(x+ans%n)%n+1,y=(y+ans%n)%n+1; //不能用上面那个公式 否则会错
if(x>y) swap(x,y);
x--; //理由同上 转化为前缀和的过程中左端点要-1
// cout<<x<<" "<<y<<endl;
int p=x/l+(x%l!=0); //p为x所处的块的下一个块的编号
ans=p*l<y?b[p][y]:0;//p*l是x所处的块的下一个块的右端点
//p*l<y 表示x和y不在同一个块中
for(i=x,p=min(p*l,y);i<=p;i++){
//暴力处理x到x所处的块的右端点/y的内容 最多处理根号n个元素
ans=max(ans,ask(x,y,a[i]));
}
printf("%d\n",ans);
}
return 0;
}
#endif
4914 可持久化并查集
为了实现可持久化，我们的并查集中不能直接使用路径压缩，那样会破化原本的树形结构（其实貌似也可以，但我不会）。于是为了防止并查集的复杂度退化，我们使用按秩合并的方式优化并查集的find操作（这里的“秩”使用的是节点的深度，而不是节点子树的大小）。同时为了能够回复到历史状态，我们用一个可持久化线段树来维护并查集的f数组和每个节点的deep数组即可。
具体到实现上，我们采用引用递归的方式建树，因此不能用结构体来保存可持久化线段树。每次合并时将深度小的节点所在子树合并到深度大的节点后部。第i个操作需要将并查集回复到第k个操作时的状态时，只要作如下操作即可。
root[i]=root[k];
时间复杂度
空间复杂度
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=40+5;
const int INF=0x3f3f3f3f;
int n,m,op;
/*
由于存在引用递归赋值 所以不用结构体
struct SegmentTree{
int lc,rc;
}tr[maxn*maxlogn<<2];
*/
int root[maxn],f[maxn*maxlogn],tot,deep[maxn*maxlogn],ls[maxn*maxlogn<<2],rs[maxn*maxlogn<<2];
void build(int &k,int l,int r) { //注意k是引用 这个函数会生成一颗线段树
if(!k) k=++tot;
if(l==r) {
f[k]=l;
return;
}
int mid=(l+r)/2;
// build(tr[k].lc,l,mid);
// build(tr[k].rc,mid+1,r);
build(ls[k],l,mid);
build(rs[k],mid+1,r);
}
void modify(int j,int &i,int l,int r,int pos,int val) { //注意i是引用 这个函数会复制上一个状态j的线段树，然后增加一条链（即第i个状态）
//modify(root[i-1],root[i],1,n,f[r1],f[r2]);
i=++tot;
if(l==r) {
f[i]=val,deep[i]=deep[j]; //将r1接到r2后面
return;
}
// tr[i].lc=tr[j].lc,tr[i].rc=tr[j].rc;
ls[i]=ls[j],rs[i]=rs[j]; //复制节点
int mid=(l+r)/2;
// if(pos<=mid) modify(tr[j].lc,tr[i].lc,l,mid,pos,val);
// else modify(tr[j].rc,tr[j].rc,mid+1,r,pos,val);
if(pos<=mid) modify(ls[j],ls[i],l,mid,pos,val);
else modify(rs[j],rs[i],mid+1,r,pos,val);
}
int query(int k,int l,int r,int x) {
if(l==r) return k;
int mid=(l+r)/2;
// if(x<=mid) return query(tr[k].lc,l,mid,x);
// else return query(tr[k].rc,mid+1,r,x);
if(x<=mid) return query(ls[k],l,mid,x);
else return query(rs[k],mid+1,r,x);
}
void add(int i,int l,int r,int pos) {
if(l==r) {
deep[i]++;
return;
}
int mid=(l+r)/2;
// if(pos<=mid) add(tr[i].lc,l,mid,pos);
// else add(tr[i].rc,mid+1,r,pos);
if(pos<=mid) add(ls[i],l,mid,pos);
else add(rs[i],mid+1,r,pos);
}
int find(int k,int x) {
int t=query(k,1,n,x);
if(f[t]==x) return t;
return find(k,f[t]); //一定要return啊
}
int main() {
ios::sync_with_stdio(false);
//freopen("可持久化并查集.in","r",stdin);
cin>>n>>m;
int ans=0,a,b,k;
build(root[0],1,n);
for(int i=1; i<=m; i++) {
cin>>op;
if(op==1) {
cin>>a>>b;
a^=ans,b^=ans;
root[i]=root[i-1];
int r1=find(root[i],a),r2=find(root[i],b);
if(f[r1]==f[r2]) continue;
if(deep[r1]>deep[r2]) swap(r1,r2);//按秩合并
modify(root[i-1],root[i],1,n,f[r1],f[r2]); //有合并操作 则将i-1个操作时的状态复制过来 然后再做改变
if(deep[r1]==deep[r2]) add(root[i],1,n,f[r2]);
//若深度相同 任选一个节点为父节点 然后将另一个节点所在子树连接过来 这个子树上所有节点的深度deep+1即可
}
if(op==2) {
cin>>k;
k^=ans;
root[i]=root[k];
}
if(op==3) {
cin>>a>>b;
a^=ans,b^=ans;
root[i]=root[i-1]; //没有改变结构 只需要将i-1个操作时的状态复制过来即可
int r1=find(root[i],a),r2=find(root[i],b);
if(f[r1]==f[r2]) ans=1;
else ans=0;
cout<<ans<<endl;
}
}
return 0;
}
#endif
