Zoj2112 dynamic ratings (overall binary + tree array)

Title Link

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
q[tot].x=a[x];q[tot].y=1;q[tot].type=1;q[tot].id=x;    //add to  y=1
//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
Then add a new 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++) 
            if (q[i].type==2) ans[q[i].id]=L;   //Statistical answer 
        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
                add(q[i].id,q[i].y);    
                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