双向链表
1 #include 2 using namespace std; 3 4 const int maxn=100000+15; 5 int pre[maxn],nex[maxn]; 6 bool boo[maxn]; 7 int n,m; 8 int main() 9 {10 scanf("%d",&n);11 for (int i=1;i<=n;i++) pre[i]=nex[i]=0;12 for (int i=2;i<=n;i++)13 {14 int k,p;15 scanf("%d%d",&k,&p);16 if (p==0)17 {18 pre[i]=pre[k];19 nex[i]=k;20 pre[k]=i;21 nex[pre[i]]=i;22 }23 else24 {25 nex[i]=nex[k];26 pre[i]=k;27 nex[k]=i;28 pre[nex[i]]=i;29 }30 }31 scanf("%d",&m);32 for (int i=1;i<=m;i++)33 {34 int x;35 scanf("%d",&x);36 if (boo[x]) continue;37 boo[x]=true;38 n--;39 pre[nex[x]]=pre[x];40 nex[pre[x]]=nex[x];41 }42 int now=0;43 for (int i=1;i<=n;i++)44 {45 now=nex[now];46 if (i
1 #include 2 #include 3 #define MAXN 100005 4 using namespace std; 5 int n; 6 bool vis[MAXN]; 7 struct queue{ 8 int l,r,no; 9 }q[MAXN];10 int main(){11 scanf("%d",&n);12 q[1]=(queue){ 0,0,1};13 for(int i=2;i<=n;i++){14 int k,p;scanf("%d%d",&k,&p);15 if(p==0){16 q[i].l=q[k].l;q[i].r=k;17 q[q[i].l].r=i;18 q[q[i].r].l=i;19 }20 else {21 q[i].l=k;q[i].r=q[k].r;22 q[q[i].l].r=i;23 q[q[i].r].l=i;24 }25 q[i].no=i;26 }27 int m;scanf("%d",&m);28 memset(vis,0,sizeof(vis));29 while(m--){30 int x;scanf("%d",&x);31 if(vis[x]) continue;32 q[q[x].l].r=q[x].r;33 q[q[x].r].l=q[x].l;34 vis[x]=true;35 }36 int now=q[0].r;37 while(now){38 printf("%d ",q[now].no);39 now=q[now].r;40 }41 return 0;42 }
View Code
优先队列
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn=10000+15; 9 int n,m;10 int a[maxn],b[maxn],c[maxn];11 struct Node12 {13 int key,x,y;14 Node(int key=0,int x=0,int y=0):key(key),x(x),y(y) {}15 };16 const bool operator < (const Node &a,const Node &b)17 {18 return a.key>b.key;19 }20 priority_queue que;21 int f(int x,int y)22 {23 return a[x]*y*y+b[x]*y+c[x];24 }25 int main()26 {27 scanf("%d%d",&n,&m);28 for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);29 for (int i=1;i<=n;i++) que.push(Node(f(i,1),i,1));30 for (int i=1;i<=m;i++)31 {32 Node now=que.top();33 if (i
并查集
1 #include 2 using namespace std; 3 4 const int maxn=200000+15; 5 int rank[maxn],fa[maxn],n,tot; 6 map Map; 7 int found(int x) 8 { 9 if (fa[x]==x) return x;10 return fa[x]=found(fa[x]);11 }12 int merge(int x,int y)13 {14 int fx=found(x),fy=found(y);15 if (fx==fy) return 0;16 if (rank[fx]==rank[fy]) rank[fx]++;17 if (rank[fx]>rank[fy]) fa[fy]=fx;18 else fa[fx]=fy;19 return 0;20 }21 int xx[maxn],yy[maxn],sg;22 int main()23 {24 int G;25 scanf("%d",&G);26 while (G--)27 {28 scanf("%d",&n);29 Map.clear();30 tot=0;31 sg=0;32 for (int i=1;i<=n;i++)33 {34 int a,b,c;35 scanf("%d%d%d",&a,&b,&c);36 if (Map.find(a)==Map.end())37 {38 tot++;39 Map[a]=tot;40 rank[tot]=0;41 fa[tot]=tot;42 }43 if (Map.find(b)==Map.end())44 {45 tot++;46 Map[b]=tot;47 rank[tot]=0;48 fa[tot]=tot;49 }50 a=Map[a];51 b=Map[b];52 if (c==1)53 {54 merge(a,b);55 }56 else57 {58 sg++;59 xx[sg]=a;60 yy[sg]=b;61 }62 }63 bool boo=true;64 for (int i=1;i<=sg;i++)65 if (found(xx[i])==found(yy[i])) boo=false;66 if (boo) printf("YES\n");67 else printf("NO\n");68 }69 return 0;70 }
RMQ
1 #include 2 using namespace std; 3 4 const int maxn=100000+15; 5 int f[20][maxn],n,m; 6 int main() 7 { 8 scanf("%d",&n); 9 for (int i=1;i<=n;i++) scanf("%d",&f[0][i]);10 int w=(int)(log(n)/log(2));11 for (int i=1;i<=w;i++)12 for (int j=1;j<=n-(1 << i)+1;j++)13 f[i][j]=max(f[i-1][j],f[i-1][j+(1 << (i-1))]);14 scanf("%d",&m);15 while (m--)16 {17 int x,y;18 scanf("%d%d",&x,&y);19 int w=(int)(log(y-x+1)/log(2));20 printf("%d\n",max(f[w][x],f[w][y-(1 << w)+1]));21 }22 return 0;23 }
树状数组
1 int lowbit(int x){ 2 return x&-x; 3 } 4 int change(int x,int y){ 5 for (;x<=n;x+=lowbit(x)) f[x]+=y; 6 return 0; 7 } 8 int ask(int x){ 9 int ans=0;10 for (;x;x-=lowbit(x)) ans+=f[x];11 return ans;12 }
1 #include 2 #include 3 #define MAXN 200005 4 using namespace std; 5 int n,m; 6 int fa1[MAXN],fa2[MAXN]; 7 inline int lowbit(int x){ return x&-x;} 8 inline int add1(int x,int y){ 9 for(;x<=n;x+=lowbit(x)) fa1[x]+=y;10 return 0;11 }12 inline int add2(int x,int y){13 for(;x<=n;x+=lowbit(x)) fa2[x]+=y;14 return 0;15 }16 inline int ask1(int x){17 int res=0;18 for(;x;x-=lowbit(x)) res+=fa1[x];19 return res;20 }21 inline int ask2(int x){22 int res=0;23 for(;x;x-=lowbit(x)) res+=fa2[x];24 return res;25 }26 inline void add(int x,int y){add1(x,y);add2(x,x*y);}27 inline void update(int l,int r,int x){add(l,x);add(r+1,-x);}28 inline int sum(int x){ return (x+1)*ask1(x)-ask2(x);}29 inline int que(int l,int r){ return sum(r)-sum(l-1);}30 inline void fir(){31 int l,r,w;scanf("%lld%lld%lld",&l,&r,&w);32 update(l,r,w);33 }34 inline void sec(){35 int l,r;scanf("%lld%lld",&l,&r);36 int ans=que(l,r);37 printf("%lld\n",ans);38 }39 int main(){40 scanf("%d%d",&n,&m);int a;41 for(int i=1;i<=n;i++) scanf("%lld",&a),update(i,i,a);42 while(m--){43 char opt;cin>>opt;44 if(opt=='A') fir();45 if(opt=='Q') sec();46 }47 }
区间修改