Loading... ## 数据结构 --- ## 并查集 ### problem 1 #### [UVA1329 Corporative Network](https://www.luogu.org/problemnew/show/UVA1329)  #### 题解 - 注意I操作与并查集的加边操作类似 - 只需在维护父亲节点时，同时维护到父亲节点的距离即可  简单滴很 --- ## 线段树 ### problem 1 #### poj2892 题目描述： 有一个长度为n的链，初始每个点都是完好的 需要支持m个操作 - (1) D x：表示将第x个点摧毁 - (2) Q x：表示询问包含x的未被摧毁的最长子链长度 - (3) R ：表示撤销上一个D操作 - 注意每个点可能被摧毁多次 #### 题解 - 显然，每次直接修改，使用for循环判断会超时。 这时就需要使用数据结构维护。 考虑使用线段树。 - 在每个节点保存的信息 1. 区间里的点是否全都是完好的 2. 从区间左端点开始向右延伸最长完好子链 3. 从区间右端点开始向左延伸最长完好子链 修改时修改每个受影响的线段树节点 查询时拆分区间查询     --- ### problem 2 #### [线段树2](https://www.luogu.org/problemnew/show/P3373) ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=100000; ll tree[4*MAXN+10],add[4*MAXN+10],mul[4*MAXN+10],a[MAXN+10],p; void build(int k,int l,int r){ add[k]=0;mul[k]=1; if(l==r){ tree[k]=a[r]; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tree[k]=(tree[k<<1]+tree[k<<1|1])%p; } void pushdown(int k,int l,int r){ int mid=(l+r)>>1; tree[k<<1]=(tree[k<<1]*mul[k]+add[k]*(mid-l+1))%p; tree[k<<1|1]=(tree[k<<1|1]*mul[k]+add[k]*(r-mid))%p; mul[k<<1]=(mul[k]*mul[k<<1])%p; mul[k<<1|1]=(mul[k]*mul[k<<1|1])%p; add[k<<1]=(add[k<<1]*mul[k]+add[k])%p; add[k<<1|1]=(add[k<<1|1]*mul[k]+add[k])%p; mul[k]=1; add[k]=0; } void m_1(int k,int l,int r,int x,int y,ll v){ if(y<l||x>r) return; if(x<=l&&y>=r){ mul[k]=mul[k]*v%p; add[k]=add[k]*v%p; tree[k]=tree[k]*v%p; return; } pushdown(k,l,r); int mid=(l+r)>>1; m_1(k<<1,l,mid,x,y,v); m_1(k<<1|1,mid+1,r,x,y,v); tree[k]=(tree[k<<1]+tree[k<<1|1])%p; } void m_2(int k,int l,int r,int x,int y,ll v){ if(y<l||x>r) return; if(x<=l&&y>=r){ add[k]=(add[k]+v)%p; tree[k]=(tree[k]+v*(r-l+1)%p)%p; return; } pushdown(k,l,r); int mid=(l+r)>>1; m_2(k<<1,l,mid,x,y,v); m_2(k<<1|1,mid+1,r,x,y,v); tree[k]=(tree[k<<1]+tree[k<<1|1])%p; } ll query(int k,int l,int r,int x,int y){ if(y<l||x>r) return 0; if(x<=l&&y>=r){ return tree[k]%p; } pushdown(k,l,r); int mid=(l+r)>>1; return (query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y))%p; } int main(){ int n,m; cin>>n>>m>>p; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=m;i++){ int op,x,y; ll z; cin>>op; if(op==1){ cin>>x>>y>>z; m_1(1,1,n,x,y,z); } else if(op==2){ cin>>x>>y>>z; m_2(1,1,n,x,y,z); } else{ cin>>x>>y; cout<<query(1,1,n,x,y)<<endl; } } return 0; } ``` --- ## 启发式合并 ### 并查集按秩合并 ```cpp int find(int x) { while(x!=fa[x]) x=fa[x]; return x; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; while(m--) { int x,y; scanf("%d%d",&x,&y); x=find(x);y=find(y); if(x!=y) { if(siz[x]>siz[y]) swap(x,y); fa[x]=y; siz[y]+=siz[x]; } } return 0; } ``` ### problem 1 #### [[USACO14MAR] The Lazy Cow_Gold 懒惰的牛(金)](https://www.luogu.org/problemnew/show/P4876) 我没听懂。。。代码如下。 ```cpp #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #define N 210000 using namespace std; struct node{int id1,id2,d;}A[N],B[N]; struct node1{int l,r,lc,rc,d,lz;}lt[4*N]; struct node2{int x,next;}e[N*2]; int n,m,num1,num2,a[N][5],l1,l2,tl,first[2*N],len; int cmp(node x,node y) { return x.d < y.d; } int getint(){ int num = 0; char c = 0; while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') { num = num * 10 + c - '0'; c = getchar(); } return num; } void bt(int l,int r) { int now=++tl; lt[now].l=l;lt[now].r=r; lt[now].lc=lt[now].rc=lt[now].d=lt[now].lz=0; if(l<r) { int mid=(l+r)/2; lt[now].lc=tl+1;bt(l,mid); lt[now].rc=tl+1;bt(mid+1,r); } } void down(int now) { int lc=lt[now].lc,rc=lt[now].rc; if(lc) lt[lc].lz+=lt[now].lz; if(rc) lt[rc].lz+=lt[now].lz; lt[now].d+=lt[now].lz; lt[now].lz=0; } void upd(int now) { int lc=lt[now].lc,rc=lt[now].rc; if(lc && lt[lc].lz) down(lc); if(rc && lt[rc].lz) down(rc); lt[now].d=max(lt[lc].d,lt[rc].d); } void change(int now,int l,int r,int d) { int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2; if(lt[now].lz) down(now); if(lt[now].l==l && lt[now].r==r) {lt[now].lz+=d;return;} if(mid>=r) change(lc,l,r,d); else if(l>mid) change(rc,l,r,d); else change(lc,l,mid,d),change(rc,mid+1,r,d); upd(now); } int find(int now) { if(lt[now].lz) down(now); return lt[now].d; } void ins(int x,int y) { len++; e[len].x=y; e[len].next=first[x]; first[x]=len; } int main() { n = getint(); m = getint(); num1=num2=0; m*=2; for(int i=1;i<=n;i++) { for (int j = 0; j <= 2; j++) a[i][j] = getint(); int x=a[i][1]*2,y=a[i][2]*2; a[i][1]=(x+y)/2;a[i][2]=(y-x)/2; a[i][3]=a[i][1]-m;a[i][4]=a[i][2]-m; A[++num1].id1=i;A[num1].id2=1;A[num1].d=a[i][1]; B[++num2].id1=i;B[num2].id2=2;B[num2].d=a[i][2]; A[++num1].id1=i;A[num1].id2=3;A[num1].d=a[i][1]-m; B[++num2].id1=i;B[num2].id2=4;B[num2].d=a[i][2]-m; } //for(int i=1;i<=n;i++) printf("%d %d %d %d\n",a[i][1],a[i][2],a[i][3],a[i][4]); sort(A+1,A+num1+1,cmp); sort(B+1,B+num2+1,cmp); int k=1; a[A[1].id1][A[1].id2]=k; for(int i=2;i<=num1;i++) { if(A[i].d!=A[i-1].d) k++; a[A[i].id1][A[i].id2]=k; } l1=k; k=1; a[B[1].id1][B[1].id2]=k; for(int i=2;i<=num2;i++) { if(B[i].d!=B[i-1].d) k++; a[B[i].id1][B[i].id2]=k; } l2=k; len=0; for(int i=1;i<=n;i++) { ins(a[i][3],i); ins(a[i][1]+1,-i); } //for(int i=1;i<=n;i++) printf("%d %d %d %d\n",a[i][1],a[i][2],a[i][3],a[i][4]); tl=0; bt(1,l2); int ans=0; for(int i=1;i<=l1;i++) { for(k=first[i];k;k=e[k].next) { int x=e[k].x,d; if(x>0) d=a[x][0]; else {x=abs(x);d=-a[x][0];} int l=a[x][4],r=a[x][2]; change(1,l,r,d); } ans=max(ans,find(1)); } printf("%d\n",ans); return 0; } ``` ### problem 2 #### UVALive7141 无穷大的地图上有n个兵，现在给一个W*H的炸弹，一次能炸死它所在行列上所有的士兵。不能放在士兵上面。 问：一次能最多干掉多少小兵？ #### 题解 ```cpp #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<iostream> #include<vector> #define N 110000 using namespace std; struct node{int d,id1,id2;}A[N*2],B[N*2]; struct node1{int l,r,lc,rc;long long d,maxd;}lt[N*4]; vector<int> v[2*N]; int len,n,w,h,num1,num2,tot1,tot2,a[N][4]; long long ans,sx[2*N],sy[2*N]; int tl,inf=N; int cmp(void const *xx,void const *yy) { node x=*(node*)xx,y=*(node*)yy; if(x.d<y.d) return -1; return 1; } void bt(int l,int r) { int now=++tl; lt[now].l=l;lt[now].r=r; lt[now].d=lt[now].maxd=lt[now].lc=lt[now].rc=0; if(l<r) { int mid=(l+r)/2; lt[now].lc=tl+1;bt(l,mid); lt[now].rc=tl+1;bt(mid+1,r); lt[now].maxd=max(lt[lt[now].lc].maxd,lt[lt[now].rc].maxd); } else lt[now].maxd=sy[l]; } void down(int now) { int lc=lt[now].lc,rc=lt[now].rc; if(lc) lt[lc].d+=lt[now].d; if(rc) lt[rc].d+=lt[now].d; lt[now].maxd+=lt[now].d; lt[now].d=0; } int find(int now) { if(lt[now].d) down(now); return lt[now].maxd; } void upd(int now) { int lc=lt[now].lc,rc=lt[now].rc; if(lc && lt[lc].d) down(lc); if(rc && lt[rc].d) down(rc); lt[now].maxd=max(lt[lc].maxd,lt[rc].maxd); } void change(int now,int l,int r,int d) { int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2; if(lt[now].d) down(now); if(lt[now].l==l && lt[now].r==r) {lt[now].d+=d;return;} if(mid>=r) change(lc,l,r,d); else if(l>mid) change(rc,l,r,d); else change(lc,l,mid,d),change(rc,mid+1,r,d); upd(now); } int main() { int z,zu=0; scanf("%d",&z); while(z--) { zu++; scanf("%d%d%d",&n,&w,&h); tot1=tot2=0; for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); A[++tot1].d=x;A[tot1].id1=i;A[tot1].id2=0; B[++tot2].d=y;B[tot2].id1=i;B[tot2].id2=1; A[++tot1].d=x-w+1;A[tot1].id1=i;A[tot1].id2=2; B[++tot2].d=y-h+1;B[tot2].id1=i;B[tot2].id2=3; } qsort(A+1,tot1,sizeof(node),cmp); qsort(B+1,tot2,sizeof(node),cmp); a[A[1].id1][A[1].id2]=1; num1=1; for(int i=2;i<=tot1;i++) { if(A[i].d!=A[i-1].d) num1++; a[A[i].id1][A[i].id2]=num1; } a[B[1].id1][B[1].id2]=1; num2=1; for(int i=2;i<=tot2;i++) { if(B[i].d!=B[i-1].d) num2++; a[B[i].id1][B[i].id2]=num2; } for(int i=1;i<=num1;i++) sx[i]=0; for(int i=1;i<=num2;i++) sy[i]=0; for(int i=1;i<=num1;i++) v[i].clear(); for(int i=1;i<=n;i++) { int x1=a[i][0],y1=a[i][1],x2=a[i][2],y2=a[i][3]; sx[x2]++;sx[x1+1]--; sy[y2]++;sy[y1+1]--; v[x2].push_back(i); v[x1+1].push_back(-i); } ans=0; for(int i=1;i<=num1;i++) { sx[i]+=sx[i-1]; ans=max(ans,sx[i]); } for(int i=1;i<=num2;i++) { sy[i]+=sy[i-1]; ans=max(ans,sy[i]); } tl=0; bt(1,num2); for(int i=1;i<=num1;i++) { for(int j=0;j<v[i].size();j++) { int k=v[i][j],l,r; l=a[abs(k)][3];r=a[abs(k)][1]; if(k>0) change(1,l,r,-inf); else change(1,l,r,inf); } int tt=find(1); if(tt>0) ans=max(ans,tt+sx[i]); } printf("Case #%d: %lld\n",zu,ans); } return 0; } ``` Last modification：January 27, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏