1.线段树
#include<cstdio> using namespace std; int n,p,a,b,m,x,y,ans; struct node { int l,r,w,f; }tree[400001]; inline void build(int k,int ll,int rr)//建树 { tree[k].l=ll,tree[k].r=rr; if(tree[k].l==tree[k].r) { scanf("%d",&tree[k].w); return; } int m=(ll+rr)/2; build(k*2,ll,m); build(k*2+1,m+1,rr); tree[k].w=tree[k*2].w+tree[k*2+1].w; } inline void down(int k)//标记下传 { tree[k*2].f+=tree[k].f; tree[k*2+1].f+=tree[k].f; tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1); tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1); tree[k].f=0; } inline void ask_point(int k)//单点查询 { if(tree[k].l==tree[k].r) { ans=tree[k].w; return ; } if(tree[k].f) down(k); int m=(tree[k].l+tree[k].r)/2; if(x<=m) ask_point(k*2); else ask_point(k*2+1); } inline void change_point(int k)//单点修改 { if(tree[k].l==tree[k].r) { tree[k].w+=y; return; } if(tree[k].f) down(k); int m=(tree[k].l+tree[k].r)/2; if(x<=m) change_point(k*2); else change_point(k*2+1); tree[k].w=tree[k*2].w+tree[k*2+1].w; } inline void ask_interval(int k)//区间查询 { if(tree[k].l>=a&&tree[k].r<=b) { ans+=tree[k].w; return; } if(tree[k].f) down(k); int m=(tree[k].l+tree[k].r)/2; if(a<=m) ask_interval(k*2); if(b>m) ask_interval(k*2+1); } inline void change_interval(int k)//区间修改 { if(tree[k].l>=a&&tree[k].r<=b) { tree[k].w+=(tree[k].r-tree[k].l+1)*y; tree[k].f+=y; return; } if(tree[k].f) down(k); int m=(tree[k].l+tree[k].r)/2; if(a<=m) change_interval(k*2); if(b>m) change_interval(k*2+1); tree[k].w=tree[k*2].w+tree[k*2+1].w; } int main() { scanf("%d",&n);//n个节点 build(1,1,n);//建树 scanf("%d",&m);//m种操作 for(int i=1;i<=m;i++) { scanf("%d",&p); ans=0; if(p==1) { scanf("%d",&x); ask_point(1);//单点查询,输出第x个数 printf("%d",ans); } else if(p==2) { scanf("%d%d",&x,&y); change_point(1);//单点修改 } else if(p==3) { scanf("%d%d",&a,&b);//区间查询 ask_interval(1); printf("%d ",ans); } else { scanf("%d%d%d",&a,&b,&y);//区间修改 change_interval(1); } } }
2.树状数组
pos-=(pos^(pos-1))&pos;也可以换成pos-=pos&(-pos)
int Qry_tarr(int pos){ int sum=0; while(pos){ sum+=tarr[pos]; pos-=(pos^(pos-1))&pos; } return sum; } void Add_tarr(int pos,int delta){ while(pos<=n){ tarr[pos]+=delta; pos+=(pos^(pos-1))&pos; } }
3.带权并查集
#include<iostream> #include<cstdio> #define maxn 30010 using namespace std; int p,cnt[maxn],sum[maxn],fa[maxn]; char s[4]; int find(int x){ if(x==fa[x])return fa[x]; int f=fa[x]; fa[x]=find(fa[x]); cnt[x]+=cnt[f]; return fa[x]; } void merge(int x,int y){ fa[y]=x; cnt[y]+=sum[x]; sum[x]+=sum[y]; sum[y]=0; } int main(){ freopen("cube.in","r",stdin);freopen("cube.out","w",stdout); for(int i=1;i<=30000;i++)fa[i]=i,sum[i]=1; scanf("%d",&p); while(p--){ scanf("%s",s); int x,y; if(s[0]=='M'){ scanf("%d%d",&x,&y); merge(find(x),find(y)); } else { scanf("%d",&x); printf("%d ",sum[find(x)]-cnt[x]-1); } } }
4.trie树
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int trie[400001][26],len,root,tot,sum[400001]; bool p; char s[11]; void Insert(){ len=strlen(s); root=0; for(int i=0;i<len;i++){ int id=s[i]-'a'; if(!trie[root][id])trie[root][id]=++tot; sum[trie[root][id]]++; root=trie[root][id]; } } int search(){ root=0; len=strlen(s); for(int i=0;i<len;i++){ int id=s[i]-'a'; if(!trie[root][id])return 0; root=trie[root][id]; } return sum[root]; } int main(){ while(gets(s)){ if(!p){ if(strlen(s))Insert(); else p=1; } else printf("%d ",search()); } return 0; }