LOJ2402 整体二分

题目链接：

https://loj.ac/p/2402

一开始想，对每块木板二分答案，用可持久化线段树维护前i个子弹射出后的区间和。复杂度是两个log，常数非常大，而且没有什么优化空间

网上看了一圈，发现有一个常数比较小的做法是整体二分。

二分+可持久化权值线段树代码：

 1 #include
 2 #pragma GCC optimize ("-Ofast")
 3 #pragma GCC optimize("unroll-loops")
 4 using namespace std;
 5 const int N=6e5+10;
 6 int a[N],b[N],s[N],fr[N],aa[N],ans[N];
 7 int ch[N*8][2],nd=1,tr[N*8];
 8 int read()
 9 {
10     int x=0;
11     char ch=getchar();
12     while (ch<'0'||ch>'9') ch=getchar();
13     while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
14     return x;    
15 }
16 void modify(int p1,int p2,int l,int r,int x)
17 {
18     tr[p2]=tr[p1]+1;
19     if (l==r) return;
20     int mid=l+r>>1;
21     if (x<=mid)
22     {
23         ch[p2][0]=++nd;
24         ch[p2][1]=ch[p1][1];
25         modify(ch[p1][0],ch[p2][0],l,mid,x);
26     }else 
27     {
28         ch[p2][1]=++nd;
29         ch[p2][0]=ch[p1][0];
30         modify(ch[p1][1],ch[p2][1],mid+1,r,x);    
31     }
32 }
33 int query(int rt,int l,int r,int x,int y)
34 {
35     if (!rt) return 0;
36     if (l>=x&&r<=y) return tr[rt];
37     int mid=l+r>>1,ret=0;
38     if (x<=mid&&ch[rt][0]) ret=ret+query(ch[rt][0],l,mid,x,y);
39     if (y>mid&&ch[rt][1]) ret=ret+query(ch[rt][1],mid+1,r,x,y);
40     return ret;
41 }
42 int main()
43 {
44     int n,m;
45     //scanf("%d%d",&n,&m);
46     n=read();
47     m=read();
48     for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),s[i]=read();//scanf("%d%d%d",&a[i],&b[i],&s[i]);
49     fr[0]=1;
50     for (int i=1;i<=m;i++) 
51     {
52         int x;
53         //scanf("%d",&x);
54         x=read();
55         fr[i]=++nd;
56         modify(fr[i-1],fr[i],1,N,x);    
57     }
58     for (int i=1;i<=n;i++)
59     {
60         aa[i]=m+1;
61         int l=s[i],r=m;
62         while (l<=r)
63         {
64             int mid=l+r>>1;
65             int py=query(fr[mid],1,N,a[i],b[i]);
66             if (query(fr[mid],1,N,a[i],b[i])>=s[i])
67             {
68                 aa[i]=mid;
69                 r=mid-1;    
70             }else l=mid+1;
71         }
72         ans[aa[i]]++;
73     }
74     for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
75 }

整体二分代码：

 1 #include
 2 using namespace std;
 3 const int N=2e5+10;
 4 int tr[N],ans[N],a[N],b[N],c[N],d[N],id[N],a1[N],a2[N];
 5 void modify(int x,int y)
 6 {
 7     while (x<=N) tr[x]+=y,x=x+(x&(-x));    
 8 }
 9 int query(int x)
10 {
11     int ret=0;
12     while (x) ret+=tr[x],x=x-(x&(-x));
13     return ret;    
14 }
15 void solve(int l,int r,int x,int y)
16 {
17     if (l==r) 
18     {
19         ans[l]+=(y-x+1);
20         return;
21     }
22     int mid=l+r>>1;
23     for (int i=l;i<=mid;i++) modify(d[i],1);
24     int c1=0,c2=0;
25     for (int i=x;i<=y;i++)
26     {
27         int tmp=query(b[id[i]])-query(a[id[i]]-1);
28         if (tmp>=c[id[i]]) a1[++c1]=id[i];else c[id[i]]-=tmp,a2[++c2]=id[i];
29     }
30     for (int i=l;i<=mid;i++) modify(d[i],-1);
31     for (int i=x;i<=x+c1-1;i++) id[i]=a1[i-x+1];
32     for (int i=x+c1;i<=y;i++) id[i]=a2[i-x-c1+1];
33     solve(l,mid,x,x+c1-1);
34     solve(mid+1,r,x+c1,y);
35 }
36 int main()
37 {
38     int n,m;
39     scanf("%d%d",&n,&m);
40     for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]),id[i]=i;
41     for (int i=1;i<=m;i++) scanf("%d",&d[i]);
42     solve(1,m+1,1,n);
43     for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
44 }

tips：整体二分的右半边要记得消除左半边带来的影响。