【BZOJ1901】Dynamic Rankings

Description
n개수를 포함하는 서열 a[1], a[2], a[3]...a[n]를 정하면 프로그램은 반드시 이런 질문에 대답해야 한다. 정해진 i, j, k에 대해 a[i], a[i+1], a[i+2]......a[j]에서 작은 k가 얼마(1≤k≤j-i+1)인지, 그리고 a[i]의 값을 바꿀 수 있다. 바꾸면 프로그램은 바뀐 a에 대해 계속 위의 질문에 대답할 수 있다.입력 파일에서 시퀀스 a를 읽고, 질문 명령과 수정 명령을 포함한 일련의 명령을 읽는 프로그램을 만들어야 한다.모든 질문 지령에 대해, 너는 반드시 정확한 대답을 출력해야 한다.첫 번째 줄에는 두 개의 정수 n(1≤n≤10000), m(1≤m≤10000)이 있다.서열의 길이와 명령의 개수를 각각 나타낸다.두 번째 줄에는 n개의 수가 있는데 a[1], a[2]......a[n]을 나타낸다. 이 수는 모두 10^9보다 작다.다음 m행은 각 명령을 설명하고 각 행의 형식은 다음 두 가지 형식 중의 하나이다.Q i jk 또는 C i t Q i jk(i, j, k는 숫자, 1≤i ≤ j≤ n, 1≤ k≤ j-i+1)는 문의 지령을 표시하고, a[i], a[i+1]......a[j]에서 k가 작은 수를 묻는다.Cit(1≤i≤n, 0≤t≤10^9)는 a[i]를 t로 바꾸는 것을 의미한다.
Input
매번 질문할 때마다, 너는 그의 답안을 출력해야 한다. 모든 출력은 단독 줄을 차지한다.
Output
출력 파일에는 T행이 포함되어야 합니다.각 그룹의 데이터에 대해 이 관문이 풀리면 한 줄의Yes를 출력한다.그렇지 않으면 No 행을 내보냅니다.
Sample Input
5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3
Sample Output
3 6
HINT
20%의 데이터 중 m, n≤100;40%의 데이터 중 m, n≤1000;100% 데이터 중 m, n≤10000.
【분석】
누드의 주석 나무는 직접 틀에 올라가면 된다.

  1 /**************************************************************

  2     Problem: 1901

  3     User: TCtower

  4     Language: C++

  5     Result: Accepted

  6     Time:612 ms

  7     Memory:24988 kb

  8 ****************************************************************/

  9  

 10 #include <iostream>

 11 #include <cstring>

 12 #include <cstdio>

 13 #include <cmath>

 14 #include <cstring>

 15 #include <algorithm>

 16 #include <vector>

 17 //#define LOCAL

 18 const int maxn=10000+5;

 19 const int INF=99999999;

 20 const int maxnode=2000000+10; 

 21 using namespace std;

 22 struct OP

 23 {

 24        int type;//0    ,1     

 25        int l,r,k;

 26 }op[maxn];

 27 //     

 28 struct node

 29 {

 30        int ls,rs,w;

 31        node(){ls=rs=w=0;}

 32 }T[maxnode];

 33 vector<int>LX;

 34 vector<int>Q1,Q2;

 35 int a[maxn],n,q,n1;

 36 int cnt,root[maxn*2]; 

 37  

 38 void init();

 39 void work();

 40 //      

 41 inline int lowbit(int i){return i&-i;}

 42 inline int find(int i)

 43 {

 44        //        

 45        return (lower_bound(LX.begin(),LX.begin()+n1,i)-LX.begin())+1;

 46 }

 47 void build(int &i,int l,int r,int val);

 48 void query(int l,int r,int k);//   k  

 49 //              ？ 

 50 int Qy(vector<int>Q1,vector<int>Q2,int l,int r,int k);

 51 void my_ins(int pos,int x,int v);

 52 void ins(int &i,int l,int r,int x,int v);

 53  

 54 int main() 

 55 {

 56     #ifdef LOCAL 

 57     freopen("data.txt","r",stdin);

 58     freopen("out.txt","w",stdout);

 59     #endif

 60     init();//       

 61     work();

 62     return 0;

 63 }

 64 void init()

 65 {

 66     scanf("%d%d",&n,&q);

 67     LX.clear();

 68     for (int i=1;i<=n;i++)

 69     {

 70         scanf("%d",&a[i]);        

 71         LX.push_back(a[i]);

 72     }

 73     char str[10];

 74     for (int i=1;i<=q;i++)

 75     {

 76         scanf("%s",str);

 77         if (str[0]=='Q')

 78         {

 79             op[i].type=0;

 80             scanf("%d%d%d",&op[i].l,&op[i].r,&op[i].k);

 81         }

 82         else

 83         {

 84             op[i].type=1;

 85             scanf("%d%d",&op[i].l,&op[i].r);

 86             LX.push_back(op[i].r);

 87         }

 88     }

 89     sort(LX.begin(),LX.end());

 90     n1=unique(LX.begin(),LX.end())-LX.begin();

 91 }

 92 void ins(int &i,int l,int r,int x,int v)

 93 {

 94      if (i==0) {T[++cnt]=T[i];i=cnt;}//         

 95      T[i].w+=v;

 96      if (l==r) return;

 97      int mid=(l+r)>>1;

 98      if (x<=mid) ins(T[i].ls,l,mid,x,v);

 99      else ins(T[i].rs,mid+1,r,x,v); 

100 }

101 void my_ins(int pos,int x,int v)

102 {

103      int t=find(x);//  x   

104      for (int i=pos;i<=n;i+=lowbit(i))

105      {

106          ins(root[i],1,n1,t,v);

107      } 

108 }

109 int Qy(vector<int>Q1,vector<int>Q2,int l,int r,int k) 

110 {

111     if (l==r) return l;

112     int c=0,mid=(l+r)>>1;

113     //       ，     

114     for (int i=0;i<Q1.size();i++) c-=T[T[Q1[i]].ls].w;

115     for (int i=0;i<Q2.size();i++) c+=T[T[Q2[i]].ls].w;

116     //  k             

117     for (int i=0;i<Q1.size();i++) Q1[i]=(c>=k?T[Q1[i]].ls:T[Q1[i]].rs);

118     for (int i=0;i<Q2.size();i++) Q2[i]=(c>=k?T[Q2[i]].ls:T[Q2[i]].rs);

119     if (c>=k) return Qy(Q1,Q2,l,mid,k);//       

120     else return Qy(Q1,Q2,mid+1,r,k-c);

121 } 

122 void query(int l,int r,int k)

123 {

124      Q1.clear();Q2.clear();//      

125      Q1.push_back(root[l!=1?l-1+n:0]);

126      Q2.push_back(root[r+n]); 

127      for (int i=l-1;i;i-=lowbit(i)) Q1.push_back(root[i]);

128      for (int i=r;i;i-=lowbit(i)) Q2.push_back(root[i]);

129      int t=Qy(Q1,Q2,1,n1,k);

130      printf("%d
",LX[t-1]);

131 } 

132 void work()

133 {

134      cnt=0;

135      memset(root,0,sizeof(root));

136      for (int i=1;i<=n;i++)

137      {

138          root[i+n]=root[i+n-1];

139          int t=find(a[i]);

140          build(root[i+n],1,n1,t);

141      }

142      for (int i=1;i<=q;i++)

143      {

144          if (op[i].type==0)

145          query(op[i].l,op[i].r,op[i].k);

146          else

147          {

148               my_ins(op[i].l,a[op[i].l],-1);

149               my_ins(op[i].l,op[i].r,1);

150               //   

151               a[op[i].l]=op[i].r;

152          }         

153      }

154 } 

155 void build(int &i,int l,int r,int val)

156 {

157      //          

158      //         

159      T[++cnt]=T[i];i=cnt;

160      T[i].w++;

161      if (l==r) return;

162      int mid=(l+r)>>1;

163      //       

164      if (val<=mid) build(T[i].ls,l,mid,val);

165      else build(T[i].rs,mid+1,r,val);

166 }