赞
踩
注意1:记得空间初始化为n就可以了,内部自动开辟n+1空间
struct BIT { int n; vector<int>vec; BIT(int len=0) { n=len; vec.resize(n+1,0); } int pre(int x) { int sum=0; while(x) sum+=vec[x] , x-=lowbit(x); return sum; } void add(int x,int v) { while(x<=n) vec[x]+=v , x+=lowbit(x); } int segment_sum(int l,int r) { return pre(r)-pre(l-1); } };
struct BIT { int n; vector<int>vec; BIT(int len=0) { n=len; vec.resize(n+1); } int pre(int pos) { int sum=0; while(pos) sum+=vec[pos],pos-=lowbit(pos); return sum; } void add(int pos,int value) { while(pos<=n) vec[pos]+=value,pos+=lowbit(pos); } void range_add(int l,int r,int value) { add(l,value),add(r+1,-value); } };
struct Bit { vector<int>sum1,sum2; int n; Bit(int x=0) { n=x; sum1.resize(n+1); sum2.resize(n+1); } void add(int p,int x) { for(int i=p;i<=n;i+=lowbit(i)) sum1[i]+=x,sum2[i]+=x*p; } void range_add(int l,int r,int x) { add(l,x),add(r+1,-x); } int ask(int p) { int res=0; for(int i=p;i;i-=lowbit(i)) res+=(p+1)*sum1[i]-sum2[i]; return res; } int range_ask(int l,int r) { return ask(r)-ask(l-1); } };
sum1[i]=d[i] ,sum2[i]=d[i]∗i
struct SegmentTree1 { vector<int>vec; SegmentTree(vector<int> &a){ int n=a.size(); vec.resize(n<<2); function<void(int,int,int)>build=[&](int p,int l,int r){ if(l==r){ vec[p]=a[l-1]; return ; } int mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); up(p); }; build(1,1,n); } void up(int p){ vec[p]=min(vec[p*2],vec[p*2+1]); } void add(int p,int l,int r,int x,int v){ if(l==r){ vec[p]=v; return ; } int mid=(l+r)>>1; if(x<=mid) add(p*2,l,mid,x,v); else add(p*2+1,mid+1,r,x,v); up(p); } int sum(int p,int l,int r,int x,int y){ if(x<=l&&r<=y) return vec[p]; int mid=(l+r)>>1,res=inf; if(x<=mid) res=min(res,sum(p*2,l,mid,x,y)); if(mid<y) res=min(res,sum(p*2+1,mid+1,r,x,y)); return res; } };
struct SegmentTree2 { vector<int>s,col; SegmentTree2(vector<int> &a){ int n=a.size(); s.resize(n*4); col.resize(n*4); function<void(int,int,int)>build=[&](int p,int l,int r){ if(l==r){ s[p]=a[l-1]; return ; } int mid=(l+r)>>1; build(1,l,mid); build(1,mid+1,r); up(p); }; build(1,1,n); } void up(int p){ s[p]=max(s[p*2],s[p*2+1]); } void down(int p,int l,int r){ if(col[p]){ s[p*2]=col[p]; s[p*2+1]=col[p]; col[p*2]=col[p]; col[p*2+1]=col[p]; col[p]=0; } } void modify(int p,int l,int r,int x,int y,int v){ if(x<=l&&r<=y){ s[p]=v; col[p]=v; return ; } down(p,l,r); int mid=(l+r)/2; if(x<=mid) modify(p*2,l,mid,x,y,v); if(y>mid) modify(p*2+1,mid+1,r,x,y,v); up(p); } int query(int p,int l,int r,int x,int y){ if(x<=l&&r<=y) return s[p]; down(p,l,r); int mid=(l+r)/2,res=0; if(x<=mid) res=max(res,query(p*2,l,mid,x,y)); if(y>mid) res=max(res,query(p*2+1,mid+1,r,x,y)); return res; } };
struct SegmentTree2 { vector<int>s,col; SegmentTree2(vector<int> a) { int n=a.size(); s.resize(n*4); col.resize(n*4); function<void(int,int,int)>build=[&](int p,int l,int r) { if(l==r) { s[p]=a[l-1]; return ; } int mid=(l+r)>>1; build(1,l,mid); build(1,mid+1,r); up(p); }; build(1,1,n); } void up(int p) { s[p]=min(s[p*2],s[p*2+1]); } void down(int p,int l,int r) { if(col[p]) { int mid=(l+r)>>1; solve(p<<1,col[p]); solve(p<<1|1,col[p]); col[p]=0; } } void solve(int p,int v) { s[p]+=v; col[p]+=v; } void modify(int p,int l,int r,int x,int y,int v) { if(x<=l&&r<=y) { solve(p,v); return ; } down(p,l,r); int mid=(l+r)/2; if(x<=mid) modify(p*2,l,mid,x,y,v); if(y>mid) modify(p*2+1,mid+1,r,x,y,v); up(p); } int query(int p,int l,int r,int x,int y) { if(x<=l&&r<=y) return s[p]; down(p,l,r); int mid=(l+r)/2,res=inf; if(x<=mid) res=min(res,query(p*2,l,mid,x,y)); if(y>mid) res=min(res,query(p*2+1,mid+1,r,x,y)); return res; } };
struct SegmentTree2 { vector<int>s,col; SegmentTree2(vector<int> &a) { int n=a.size(); s.resize(n*4); col.resize(n*4); function<void(int,int,int)>build=[&](int p,int l,int r) { if(l==r) { s[p]=a[l-1]; return ; } int mid=(l+r)>>1; build(1,l,mid); build(1,mid+1,r); up(p); }; build(1,1,n); } void down(int p, int l, int r) { if (col[p]) { int mid = l + r >> 1; solve(p<<1,l,mid,col[p]); solve(p<<1|1,mid+1,r,col[p]); col[p] = 0; } } void up(int p) { s[p] = s[p * 2] + s[p * 2 + 1]; } void solve(int p,int l,int r,int value) { s[p] += (r - l + 1) * value; col[p] += value; } void modify(int p, int l, int r, int L, int R, int value) { if (L <= l && r <= R) { solve(p,l,r,value); return ; } down(p, l, r); int mid = l + r >> 1; if (L <= mid) modify(p * 2, l, mid, L, R, value); if (mid < R) modify(p * 2 + 1, mid + 1, r, L, R, value); up(p); } int query(int p, int l, int r, int L, int R) { if (L <= l && r <= R) return s[p]; down(p, l, r); int mid = l + r >> 1, sum = 0; if (L <= mid) sum += query(p * 2, l, mid, L, R); if (mid < R) sum += query(p * 2 + 1, mid + 1, r, L, R); s[p] = s[p * 2] + s[p * 2 + 1]; return sum; } };
·
一种可重复贡献的数据结构,满足结合律。
类似问题:区间最值,区间按位与,区间按位或
倍增RMQ
第一步:构造RMQ,变量为n。
第二步:记得ST表值初始化为inf/-inf,以及2^0倍赋值和转移方程的max/min修改
struct RMQ { vector<vector<int> >ST; RMQ(int n=0) { ST.resize(n+1,vector<int>(21,inf)); for(int i=1;i<=n;i++) ST[i][0]=pre[i]; for(int i=1;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++) ST[j][i]=min(ST[j][i-1],ST[j+(1<<i-1)][i-1]); } int query(int l,int r) { int k=log2(r-l+1); return min(ST[l][k],ST[r-(1<<k)+1][k]); } };
const int N=5e4+5;
int a[N],n,m,num,block;
int l[N],r[N],belong[N],tag[N];
void init()
{
block=sqrt(n);
num=ceil(n*1.0/block);
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for(int i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
}
const int N=1e6+5; int a[N],cnt[N],belong[N],block,sum=0,ans[N]; struct node { int l,r,pos; bool operator<(const node &b)const { return belong[l]==belong[b.l]?r<b.r:belong[l]<belong[b.l]; } } s[N]; void add(int pos) { if(!cnt[a[pos]]) ++sum; ++cnt[a[pos]]; } void del(int pos) { --cnt[a[pos]]; if(!cnt[a[pos]]) --sum; }
进行分块
block=sqrt(n);
for(int i=1; i<=n; ++i)
belong[i]=(i-1)/block+1;
双指针移动
int l=1,r=0;
for(int i=0; i<m; ++i)
{
int ql=s[i].l,qr=s[i].r;
while(l<ql)
del(l++);
while(l>ql)
add(--l);
while(r<qr)
add(++r);
while(r>qr)
del(r--);
ans[s[i].pos]=sum;
}
1:移动指针常数优化,大概200ms
while(l < ql)
sum -= !--cnt[a[l++]];
while(l > ql)
sum += !cnt[a[--l]]++;
while(r < qr)
sum += !cnt[a[++r]]++;
while(r > qr)
sum -= !--cnt[a[r--]];
2:玄学奇偶性排序,大概200ms
return (belong^b.belong)?belong<b.belong:((belong&1)?r<b.r:r> b.r);
玄学
bool operator<(const node& b)
{
if(belong==b.belong)
return r<b.r;
return l<b.l;
}
3:快读,快输优化
int read() { int res = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar(); return res; } void printi(int x) { if(x / 10) printi(x / 10); putchar(x % 10 + '0'); }
4:分块优化
O(
n
2
3
n^{\frac2 3}
n32)
int num=n/sqrt(m*2.0/3);
5:开O2
const int N=5e5+5; namespace zhuxi { struct node { int left,right,value; }s[N*40]; int cnt=0,root[N]; void modify(int l,int r,int pre,int &now,int value) { s[++cnt]=s[pre]; now=cnt; s[cnt].value++; if(l==r) return ; int mid=(l+r)>>1; if(value<=mid) modify(l,mid,s[pre].left,s[now].left,value); else modify(mid+1,r,s[pre].right,s[now].right,value); } int query(int l,int r,int L,int R,int k) { if(l==r) return l; int mid=(l+r)>>1; int temp=s[s[R].left].value-s[s[L].left].value; if(k<=temp) return query(l,mid,s[L].left,s[R].left,k); else return query(mid+1,r,s[L].right,s[R].right,k-temp); } }
const int N =2e5+5; int n,m,root[N],cnt; struct node { int l,r,fat,Size; } s[N*30]; void build(int& p,int l,int r) { p=++cnt; if(l==r) { s[p].fat=l; s[p].Size=1; return; } int mid=l+r>>1; build(s[p].l,l,mid); build(s[p].r,mid+1,r); } pair<int,int> query(int p,int l,int r,int pos) { if(l==r) return {s[p].fat,s[p].Size}; int mid=l+r>>1; if(pos<=mid) return query(s[p].l,l,mid,pos); else return query(s[p].r,mid+1,r,pos); } void update(int pre,int &p,int l,int r,int pos,int Fat,int sum) { p=++cnt; s[p]=s[pre]; if(l==r) { s[p].Size=sum; s[p].fat=Fat; return; } int mid=l+r>>1; if (pos<=mid) update(s[pre].l,s[p].l,l,mid,pos,Fat,sum); else update(s[pre].r,s[p].r,mid+1,r,pos,Fat,sum); } pair<int,int> find(int root,int pos) { pair<int,int> ans=query(root,1,n,pos); if (ans.F==pos) return ans; else return find(root,ans.F); } int main() { cin>>n>>m; build(root[0], 1, n);///初始化 for (int i=1;i<=m;i++) { int ty; cin>>ty; if(ty==1)///x-y合并 { root[i]=root[i-1]; int x,y; cin>>x>>y; pair<int,int> tx=find(root[i],x); pair<int,int> ty=find(root[i],y); if(tx.F==ty.F) continue;//已经是一起的 if(tx.S>ty.S) swap(tx,ty); update(root[i],root[i],1,n,tx.F,ty.F,0); update(root[i],root[i],1,n,ty.F,ty.F,tx.S+ty.S); } else if(ty==2)///操作i回到x版本 { int x; cin>>x; root[i]=root[x]; } else///判断x与y是否同一集合 { root[i]=root[i-1]; int x,y; cin>>x>>y; cout<<(find(root[i],x)==find(root[i], y))<<endl; } } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。