# Zoj2112 dynamic ratings (overall binary + tree array)

analysis:
This problem has modification operations, so we need to do something about the operation processing:
To modify an operation, we will change it into two operations: delete and add

```scanf("%d%d",&x,&y);
tot++;
q[tot].x=a[x];q[tot].y=-1;q[tot].type=1;q[tot].id=x;   //delete  y=-1
tot++;
a[x]=y;   //Maintenance sequence status
//x:value  id:Position in array ```

We need an auxiliary array a to record the sequence state
In case of modification, we need to delete the previous number

#### Note: be sure to maintain the a array

Main program and poj2104 equally

```//Write code here
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int INF=1e9+7;
const int N=50010;
const int MM=10010;
struct node{
int x,y,k,type,id;
};
node q[N+MM<<1],q1[N+MM<<1],q2[N+MM<<1];
int n,m,t[N],tot,totx,ans[N],a[N];

void add(int x,int z) {for (int i=x;i<=n;i+=(i&(-i))) t[i]+=z;}
int ask(int x) {int ans=0;for (int i=x;i>0;i-=(i&(-i))) ans+=t[i];return ans;}

void solve(int ql,int qr,int L,int R)
{
if (ql>qr) return;
if (L==R)
{
for (int i=ql;i<=qr;i++)
return;
}

int M=(L+R)>>1;   //The judgment standard of this time
int t1=0,t2=0;
for (int i=ql;i<=qr;i++)
{
if (q[i].type==1)
{
if (q[i].x<=M){      //In this casexContribute to ranking
q1[t1++]=q[i];
}
else q2[t2++]=q[i];  //xNo contribution to ranking
}
else
{
int tt=ask(q[i].y)-ask(q[i].x-1);       //How much of the current interval is less than M Value of
if (tt>=q[i].k) q1[t1++]=q[i];
else
{
q[i].k-=tt;
q2[t2++]=q[i];
}
}
}

for (int i=0;i<t1;i++) q[ql+i]=q1[i];           //hold q1,q2 Copy information from toqin
for (int i=0;i<t2;i++) q[ql+t1+i]=q2[i];
for (int i=0;i<t1;i++)
if (q1[i].type==1) add(q1[i].id,-q1[i].y);  //Remove the previous marks

solve(ql,ql+t1-1,L,M);
solve(ql+t1,qr,M+1,R);
}

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(t,0,sizeof(t));
memset(ans,0,sizeof(ans));
totx=0; tot=0;

scanf("%d%d",&n,&m);
int x,y,k;
char s[5];
for (int i=1;i<=n;i++)
{
scanf("%d",&x); a[i]=x;
tot++;
q[tot].x=x;q[tot].y=1;q[tot].type=1;q[tot].id=i;
//x:value  id:Position in array
}
for (int i=1;i<=m;i++)
{
scanf("%s",s);
if (s[0]=='Q'){
scanf("%d%d%d",&x,&y,&k);
tot++;
q[tot].x=x;q[tot].y=y;q[tot].k=k;q[tot].type=2;q[tot].id=++totx;
}
else{
scanf("%d%d",&x,&y);
tot++;
q[tot].x=a[x];q[tot].y=-1;q[tot].type=1;q[tot].id=x;
tot++;
a[x]=y;
q[tot].x=a[x];q[tot].y=1;q[tot].type=1;q[tot].id=x;
//x:value  id:Position in array
}
}

solve(1,tot,0,INF);
for (int i=1;i<=totx;i++) printf("%d\n",ans[i]);
}
return 0;
}```

Tags: less

Posted on Mon, 11 May 2020 08:55:20 -0700 by charliepage