整体二分QAQ

POJ 2104 K-th Number

题意：

给出一个序列，每次查询区间第k小

分析：

整体二分入门题？

代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 //by NeighThorn
 6 #define inf 0x3f3f3f3f
 7 using namespace std;
 8 
 9 const int maxn=100000+5,maxm=5000+5;
10 
11 int n,m,a[maxn],ans[maxm],tr[maxn];
12 
13 struct M{
14     int x,y,k,id,flag;    
15     M(int a=0,int b=0,int c=0,int d=0,int e=0){
16         x=a,y=b,k=c,id=d,flag=e;
17     }
18 }q[maxm+maxn],q1[maxm+maxn],q2[maxm+maxn];
19 
20 inline void add(int x,int y){
21     for(;x<=n;x+=x&(-x))
22         tr[x]+=y;    
23 }
24 
25 inline int query(int x){
26     int res=0;
27     for(;x;x-=x&(-x))
28         res+=tr[x];
29     return res;    
30 }
31 
32 inline void solve(int L,int R,int l,int r){
33     if(L>R)
34         return;
35     if(l==r){
36         for(int i=L;i<=R;i++)
37             if(q[i].flag==2)
38                 ans[q[i].id]=l;
39         return;
40     }
41     int mid=(l+r)>>1,l1=0,l2=0;
42     for(int i=L;i<=R;i++){
43         if(q[i].flag==1){
44             if(q[i].x<=mid)
45                 add(q[i].id,1),q1[l1++]=q[i];
46             else
47                 q2[l2++]=q[i];
48         }
49         else{
50             int lala=query(q[i].y)-query(q[i].x-1);
51             if(lala>=q[i].k)
52                 q1[l1++]=q[i];
53             else
54                 q[i].k-=lala,q2[l2++]=q[i];
55         }    
56     }
57     for(int i=0;i<l1;i++)
58         if(q1[i].flag==1)
59             add(q1[i].id,-1);
60     memcpy(q+L,q1,sizeof(q[0])*l1);
61     memcpy(q+L+l1,q2,sizeof(q[0])*l2);
62     solve(L,L+l1-1,l,mid);solve(L+l1,R,mid+1,r);
63 }
64 
65 signed main(void){
66     while(scanf("%d%d",&n,&m)!=EOF){
67         memset(tr,0,sizeof(tr));
68         for(int i=1;i<=n;i++){
69             scanf("%d",&a[i]);
70             q[i]=(M){a[i],1,0,i,1};
71         }
72         for(int i=1;i<=m;i++)
73             scanf("%d%d%d",&q[i+n].x,&q[i+n].y,&q[i+n].k),q[i+n].id=i,q[i+n].flag=2;
74         solve(1,n+m,-inf,inf);
75         for(int i=1;i<=m;i++)
76             printf("%d
",ans[i]);
77     }
78     return 0;    
79 }

BZOJ 1901: Zju2112 Dynamic Rankings

时空隧道

分析：

和上一题一样，就是把修改操作拆成删除和插入操作...

代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 //by NeighThorn
 6 #define inf 0x3f3f3f3f
 7 using namespace std;
 8  
 9 const int maxn=10000+5;
10  
11 int n,m,cnt,tot,tr[maxn],pre[maxn],ans[maxn];
12  
13 char ch[3];
14  
15 struct M{
16     int x,y,k,id,flag;  
17 }q[maxn*4],q1[maxn*4],q2[maxn*4];
18  
19 inline int read(void){
20     char ch=getchar();int f=1,x=0;
21     while(!(ch>='0'&&ch<='9')){
22         if(ch=='-')
23             f=-1;
24         ch=getchar();
25     }   
26     while(ch>='0'&&ch<='9')
27         x=x*10+ch-'0',ch=getchar();
28     return x;
29 }
30  
31 inline void insert(int x,int y){
32     for(;x<=n;x+=x&(-x))
33         tr[x]+=y;   
34 }
35  
36 inline int query(int x){
37     int res=0;
38     for(;x;x-=x&(-x))
39         res+=tr[x];
40     return res; 
41 }
42  
43 inline void solve(int L,int R,int l,int r){
44     if(L>R)
45         return;
46     if(l==r){
47         for(int i=L;i<=R;i++)
48             if(q[i].flag==2)
49                 ans[q[i].id]=l;
50         return;
51     }
52     int mid=(l+r)>>1,l1=0,l2=0;
53     for(int i=L;i<=R;i++){
54         if(q[i].flag==1){
55             if(q[i].x<=mid)
56                 insert(q[i].id,q[i].y),q1[l1++]=q[i];
57             else
58                 q2[l2++]=q[i];
59         }
60         else{
61             int lala=query(q[i].y)-query(q[i].x-1);
62             if(lala>=q[i].k)
63                 q1[l1++]=q[i];
64             else
65                 q[i].k-=lala,q2[l2++]=q[i]; 
66         }
67     }
68     for(int i=0;i<l1;i++)
69         if(q1[i].flag==1)
70             insert(q1[i].id,-q1[i].y);
71     memcpy(q+L,q1,sizeof(q[0])*l1);
72     memcpy(q+L+l1,q2,sizeof(q[0])*l2);
73     solve(L,L+l1-1,l,mid);solve(L+l1,R,mid+1,r);
74 }
75  
76 signed main(void){
77     n=read(),m=read();tot=n;
78     for(int i=1;i<=n;i++)
79         pre[i]=read(),q[i].x=pre[i],q[i].y=1,q[i].k=0,q[i].id=i,q[i].flag=1;
80     for(int i=1,x,y;i<=m;i++){
81         scanf("%s",ch);tot++;
82         if(ch[0]=='Q')
83             q[tot].x=read(),q[tot].y=read(),q[tot].k=read(),q[tot].id=++cnt,q[tot].flag=2;
84         else
85             x=read(),y=read(),q[tot].x=pre[x],q[tot].y=-1,q[tot].k=0,q[tot].id=x,q[tot].flag=1,
86             pre[x]=y,q[++tot].x=y,q[tot].y=1,q[tot].k=0,q[tot].id=x,q[tot].flag=1;
87     }
88     solve(1,tot,0,inf);
89     for(int i=1;i<=cnt;i++)
90         printf("%d
",ans[i]);
91     return 0;
92 }//Cap ou pas cap. Cap.

BZOJ 3110: [Zjoi2013]K大数查询

时空隧道

分析：

还是一样的...只是把树状数组改成了线段树...

然而...虽然题水...但是我WA了半页...快读写错了...没有读入负数

代码：

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 //by NeighThorn
  6 #define int long long 
  7 using namespace std;
  8  
  9 const int maxn=50000+5;
 10  
 11 int n,m,cnt,ans[maxn];
 12  
 13 struct M{
 14     int x,y,id,flag;    
 15     long long k;
 16 }q[maxn],q1[maxn],q2[maxn];
 17  
 18 struct Tree{
 19     int l,r;
 20     long long sum,lazy; 
 21 }tree[maxn<<2];
 22  
 23 inline long long longread(void){
 24     char ch=getchar();int f=1;long long x=0;
 25     while(!(ch>='0'&&ch<='9')){
 26         if(ch=='-')
 27             f=-1;
 28         ch=getchar();
 29     }    
 30     while(ch>='0'&&ch<='9')
 31         x=x*10+ch-'0',ch=getchar();
 32     return f*x;
 33 }
 34  
 35 inline int intread(void){
 36     char ch=getchar();int f=1,x=0;
 37     while(!(ch>='0'&&ch<='9')){
 38         if(ch=='-')
 39             f=-1;
 40         ch=getchar();
 41     }    
 42     while(ch>='0'&&ch<='9')
 43         x=x*10+ch-'0',ch=getchar();
 44     return f*x;
 45 }
 46  
 47 inline void build(int l,int r,int tr){
 48     tree[tr].l=l,tree[tr].r=r,tree[tr].sum=0,tree[tr].lazy=0;
 49     if(l==r)
 50         return;
 51     int mid=(l+r)>>1;
 52     build(l,mid,tr<<1),build(mid+1,r,tr<<1|1);
 53 }
 54  
 55 inline void change(int l,int r,int val,int tr){//cout<<l<<" "<<r<<"   "<<tree[tr].l<<" "<<tree[tr].r<<" "<<tr<<"   ";
 56     if(tree[tr].l==l&&tree[tr].r==r){
 57         tree[tr].sum+=val*(r-l+1);
 58         tree[tr].lazy+=val;return;  
 59     }
 60     int mid=(tree[tr].l+tree[tr].r)>>1;//cout<<mid<<endl;
 61     if(tree[tr].lazy)
 62         change(tree[tr].l,mid,tree[tr].lazy,tr<<1),change(mid+1,tree[tr].r,tree[tr].lazy,tr<<1|1),tree[tr].lazy=0;
 63     if(r<=mid)
 64         change(l,r,val,tr<<1);
 65     else if(l>mid)
 66         change(l,r,val,tr<<1|1);
 67     else
 68         change(l,mid,val,tr<<1),change(mid+1,r,val,tr<<1|1);
 69     tree[tr].sum=tree[tr<<1].sum+tree[tr<<1|1].sum;
 70 }
 71  
 72 inline long long query(int l,int r,int tr){//cout<<l<<" "<<r<<" "<<tree[tr].l<<" "<<tree[tr].r<<" "<<tr<<" ";
 73     if(tree[tr].l==l&&tree[tr].r==r)
 74         return tree[tr].sum;
 75     int mid=(tree[tr].l+tree[tr].r)>>1;//cout<<mid<<endl;
 76     if(tree[tr].lazy)
 77         change(tree[tr].l,mid,tree[tr].lazy,tr<<1),change(mid+1,tree[tr].r,tree[tr].lazy,tr<<1|1),tree[tr].lazy=0;
 78     if(r<=mid)
 79         return query(l,r,tr<<1);
 80     else if(l>mid)
 81         return query(l,r,tr<<1|1);
 82     else
 83         return query(l,mid,tr<<1)+query(mid+1,r,tr<<1|1);
 84 }
 85  
 86 inline void solve(int L,int R,int l,int r){//cout<<L<<" "<<R<<" "<<l<<" "<<r<<endl;
 87     if(L>R)
 88         return;
 89     if(l==r){
 90         for(int i=L;i<=R;i++)
 91             if(q[i].flag==2)
 92                 ans[q[i].id]=l;
 93         return; 
 94     }
 95     int mid=(l+r)>>1,l1=0,l2=0;
 96     for(int i=L;i<=R;i++){//cout<<i<<endl;
 97         if(q[i].flag==1){//cout<<"***"<<endl;
 98             if(q[i].k<=mid)
 99                 change(q[i].x,q[i].y,1,1),q1[l1++]=q[i];
100             else
101                 q2[l2++]=q[i];
102         }
103         else{//cout<<"&&&"<<endl;
104             int lala=query(q[i].x,q[i].y,1);//cout<<q[i].x<<" "<<q[i].y<<" "<<lala<<" "<<tree[1].sum<<endl;
105             if(lala>=q[i].k)
106                 q1[l1++]=q[i];
107             else
108                 q[i].k-=lala,q2[l2++]=q[i];
109         }
110     }//cout<<"lala"<<endl;
111     for(int i=0;i<l1;i++)
112         if(q1[i].flag==1)
113             change(q1[i].x,q1[i].y,-1,1);
114 //  memcpy(q+L,q1,sizeof(q[0])*l1);
115 //  memcpy(q+L+l1,q2,sizeof(q[0])*l2);
116     for(int i=0;i<l1;i++)
117         q[L+i]=q1[i];
118     for(int i=0;i<l2;i++)
119         q[L+l1+i]=q2[i];
120     solve(L,L+l1-1,l,mid),solve(L+l1,R,mid+1,r);
121 }
122  
123 signed main(void){
124 //  freopen("sequence10.in","r",stdin);
125 //  freopen("out.out","w",stdout); 
126     n=intread();m=intread();cnt=0;
127 //  scanf("%lld%lld",&n,&m);
128     for(int i=1,l,s,x,y;i<=m;i++){
129         l=intread();
130 //      scanf("%lld",&l);
131         if(l==1)
132             q[i].x=intread(),q[i].y=intread(),q[i].k=longread(),q[i].k=n-q[i].k+1,q[i].flag=1;
133         else
134             q[i].x=intread(),q[i].y=intread(),q[i].k=longread(),q[i].id=++cnt,q[i].flag=2;
135     }build(1,n,1);solve(1,m,1,n);
136     for(int i=1;i<=cnt;i++)
137         printf("%lld
",n-ans[i]+1);
138     return 0;
139 }//Cap ou pas cap. Cap.

BZOJ 2527: [Poi2011]Meteors

时空隧道

还是板子题...感觉我要废了TAT...

代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 //by NeighThorn
 7 using namespace std;
 8  
 9 const int maxn=300000+5;
10  
11 int n,m,k,cnt,ans[maxn],need[maxn];
12  
13 vector<int> v[maxn];
14  
15 unsigned long long tr[maxn];
16  
17 struct M{
18     int x,y,k,id,flag;  
19 }q[maxn<<2],q1[maxn<<2],q2[maxn<<2];
20  
21 inline void insert(int x,int y){
22     for(;x<=m;x+=x&(-x))
23         tr[x]+=y;   
24 }
25  
26 inline unsigned long long query(int x){
27     unsigned long long res=0;
28     for(;x;x-=x&(-x))
29         res+=tr[x];
30     return res; 
31 }
32  
33 inline void solve(int L,int R,int l,int r){
34     if(L>R)
35         return;
36     if(l==r){
37         for(int i=L;i<=R;i++)
38             if(q[i].flag==2)
39                 ans[q[i].id]=l;
40         return;
41     }
42     int mid=(l+r)>>1,l1=0,l2=0;
43     for(int i=L;i<=R;i++){
44         if(q[i].flag==1){
45             if(q[i].id<=mid)
46                 insert(q[i].x,q[i].k),insert(q[i].y+1,-q[i].k),q1[l1++]=q[i];
47             else
48                 q2[l2++]=q[i];
49         }
50         else{
51             unsigned long long lala=0;
52             for(int j=0;j<v[q[i].id].size();j++)
53                 lala+=query(v[q[i].id][j]);
54             if(lala>=q[i].k)
55                 q1[l1++]=q[i];
56             else
57                 q[i].k-=lala,q2[l2++]=q[i];
58         }
59     }
60     for(int i=0;i<l1;i++)
61         if(q1[i].flag==1)
62             insert(q1[i].x,-q1[i].k),insert(q1[i].y+1,q1[i].k);
63     for(int i=0;i<l1;i++)
64         q[L+i]=q1[i];
65     for(int i=0;i<l2;i++)
66         q[L+l1+i]=q2[i];
67     solve(L,L+l1-1,l,mid),solve(L+l1,R,mid+1,r);
68 }
69  
70 signed main(void){
71     scanf("%d%d",&n,&m);
72     for(int i=1,x;i<=m;i++)
73         scanf("%d",&x),v[x].push_back(i);
74     for(int i=1;i<=n;i++)
75         scanf("%d",&need[i]);
76     scanf("%d",&k);
77     for(int i=1,s,x,y;i<=k;i++){
78         scanf("%d%d%d",&x,&y,&s);
79         if(x<=y)
80             q[++cnt].x=x,q[cnt].y=y,q[cnt].k=s,q[cnt].flag=1,q[cnt].id=i;
81         else
82             q[++cnt].x=x,q[cnt].y=m,q[cnt].k=s,q[cnt].flag=1,q[cnt].id=i,
83             q[++cnt].x=1,q[cnt].y=y,q[cnt].k=s,q[cnt].flag=1,q[cnt].id=i;
84     }
85     for(int i=1;i<=n;i++)
86         q[++cnt].k=need[i],q[cnt].id=i,q[cnt].flag=2;
87     solve(1,cnt,1,k+1); 
88     for(int i=1;i<=n;i++){
89         if(ans[i]==k+1)
90             puts("NIE");
91         else
92             printf("%d
",ans[i]);  
93     }
94     return 0;   
95 }//Cap ou pas cap. Cap.
96

By NeighThorn