12.13 日记
奇技淫巧
判断是不是 2 的幂: x> 0 ? ( x & (x - 1)) == 0 : false
CDQ
P3374: 树状数组单点加减 + 区间查询
思考 CDQ 的时候可以按照如下思路:
假设左右区间各自内部对内部的影响已经统计完了, 并且都已经按照第二关键字 (位置) 排好序了.
那么首先, 由于已经按照第一关键字 (时间) 排好序才开始 CDQ 的, 所以左边的所有 t 都小于右边的 t, 第一维是可以保证的.
再之后, 因为左右都按第二关键字排好序了, 所以双指针, 每次取较小的那一个, 则之后的元素一定比刚取走的那个大 (或者等于).
接下来, 考虑实际意义, 左边区间的第一维小, 所以是先进行的操作. 那么显然, 右区间修改操作对左区间无意义 (因为还没改右边的, 左边的就已经询问完了), 左区间的修改操作对右区间的影响要看第二关键字, 如果左区间的修改操作的位置比右边的询问小, 那么是产生影响的, 具体就是把询问拆成两部分,[1,l-1] 和 [1,r], 询问到第一个就减, 询问到第二个就加. 注意离线操作是按照询问次序进行储存答案的.
另外, 如果 pos(第二关键字) 相同该怎么办? 必须再对第三关键字排序! 原理很简单, 根据实际意义, 肯定是先统计修改, 再处理询问操作, 不然就会漏.
我就是挂在这两个地方.
- #include<bits/stdc++.h>
- using namespace std;
- const int M=5e5+20;
- #define mid ((l+r)>>1)
- #define LL long long
- struct C{
- int type,pos,val;
- C(int a=0,int b=0,int c=0):type(a),pos(b),val(c){}// 若 type=1,val = 修改数值, 若 type=2/3,val = 询问位置
- bool operator<(C x){
- return pos<x.pos||(pos==x.pos&&type<x.type);
- }
- }v[M*3],tmp[M*3];
- LL ans[M];
- int cnt;
- void CDQ(int l,int r){
- if (l==r)
- return;
- CDQ(l,mid),CDQ(mid+1,r);
- int i=l,j=mid+1,k=l;
- LL sum=0;
- while(i<=mid&&j<=r)
- if (v[i]<v[j]){
- if (v[i].type==1)
- sum+=v[i].val;
- tmp[k++]=v[i++];
- }
- else{
- if (v[j].type==2)
- ans[v[j].val]-=sum;
- else if (v[j].type==3)
- ans[v[j].val]+=sum;
- tmp[k++]=v[j++];
- }
- while(i<=mid)
- tmp[k++]=v[i++];
- while(j<=r){
- if (v[j].type==2)
- ans[v[j].val]-=sum;
- else if (v[j].type==3)
- ans[v[j].val]+=sum;
- tmp[k++]=v[j++];
- }
- for(int i=l;i<=r;++i)
- v[i]=tmp[i];
- }
- int main(){
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i){
- int c;
- scanf("%d",&c);
- v[++cnt]=C(1,i,c);
- }
- for(int i=1;i<=m;++i){
- int op,x,y;
- scanf("%d%d%d",&op,&x,&y);
- if (op==1)
- v[++cnt]=C(1,x,y);
- else
- v[++cnt]=C(2,x-1,i),
- v[++cnt]=C(3,y,i);
- }
- CDQ(1,cnt);
- for(int i=1;i<=m;++i)
- if (ans[i])
- printf("%lld\n",ans[i]);
- return 0;
- }
P3810: 三维偏序
还需要去重才行.
- #include<bits/stdc++.h>// 还需要去重
- using namespace std;
- const int M=5e5+20;
- #define mid ((l+r)>>1)
- struct C{
- int a,b,c,no;
- C(int d=0,int e=0,int f=0,int g=0):a(d),b(e),c(f),no(g){}
- bool operator<(const C &x)const{
- if (a!=x.a)
- return a<x.a;
- else if (b!=x.b)
- return b<x.b;
- return c<x.c;
- }
- }v[M],ca[M];
- int n,k,c[M*2],ans[M],res[M];
- inline int lowbit(int x){return x&(-x);}
- inline void operate(int x,int kk){
- for(int i=x;i<=2e5;i+=lowbit(i))
- c[i]+=kk;
- }
- inline int query(int x){//1-x 的和
- int ans=0;
- for(int i=x;i;i-=lowbit(i))
- ans+=c[i];
- return ans;
- }
- void CDQ(int l,int r){
- if (l==r)
- return;
- CDQ(l,mid),CDQ(mid+1,r);
- int i=l,j=mid+1,kk=l;
- while(i<=mid&&j<=r)
- if(v[i].b<=v[j].b)
- operate(v[i].c,1),
- ca[kk++]=v[i++];
- else
- ans[v[j].no]+=query(v[j].c),
- ca[kk++]=v[j++];
- while(i<=mid)
- operate(v[i].c,1),
- ca[kk++]=v[i++];
- while(j<=r)
- ans[v[j].no]+=query(v[j].c),
- ca[kk++]=v[j++];
- for(int a=l;a<=mid;++a)
- operate(v[a].c,-1);
- for(int a=l;a<=r;++a)
- v[a]=ca[a];
- }
- int main(){
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;++i)
- scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c),v[i].no=i;
- sort(v+1,v+n+1);
- CDQ(1,n);
- for(int i=1;i<=n;++i)
- ++res[ans[i]];
- for(int i=1;i<=n;++i)
- printf("%d\n",ans[i]);
- for(int i=0;i<n;++i)
- printf("%d\n",res[i]);
- return 0;
- }
二逼平衡树
CDQ 做法:
1 整体二分
就是二分答案跑 cdq,
对于查询 k 大, 我们得到左边的个数 num, 如果 k<=num, 去左边, 否则 k-=num, 去右边
否则 k<=mid 分左, 否则分右边.
对于查询 rank, 我们只在 k>mid 的时候, 用 num 更新答案.
对于查询前驱, 我们只在 k>mid 的时候, 用左边的对应区间 max 更新答案 (线段树维护即可).
(我通过将所有数取反来将后继转化为前驱处理.)
此法较好实现.
设 U 为数的范围, 时间 (n+m)logUlogn. 离散后应该是 (n+m)lognlogn, 但我懒得离散..
目前拿了这题洛谷的 rank2.
核心部分:
- void solve(int L,int R,int l,int r)
- {
- if (l>r) return;
- if (L==R)
- {
- for (i=l;i<=r;++i)
- {
- x=q[i];
- if (a[x].type==2) ans[a[x].id]=L;
- }
- return;
- }
- int mid=(L+R)>>1;
- t1=t2=t3=0;
- for (i=l;i<=r;++i)
- {
- now=q[i];
- if (a[now].type==2)
- {
- num=T.qiu_s(a[now].l,a[now].r);
- if (num<a[now].x) { a[now].x-=num;q2[++t2]=now; }
- else q1[++t1]=now;
- } else
- {
- if (a[now].x>mid) q2[++t2]=now;
- else q1[++t1]=now;
- if (a[now].type==3)
- {
- if (a[now].x<=mid)
- {
- q3[++t3]=now;
- T.add(a[now].l,a[now].id,a[now].x);
- }
- } else
- if (a[now].x>mid)
- if (a[now].type==4)
- {
- chmax(ans[a[now].id],T.qiu_m(a[now].l,a[now].r));
- } else
- ans[a[now].id]+=T.qiu_s(a[now].l,a[now].r);
- }
- }
- while (t3) { now=q3[t3--];T.clear(a[now].l); }
- int k=l-1;
- for (i=1;i<=t1;++i) q[++k]=q1[i];
- for (i=1;i<=t2;++i) q[k+i]=q2[i];
- solve(L,mid,l,k);solve(mid+1,R,k+1,r);
- }
来源: http://www.bubuko.com/infodetail-3343810.html