ACM14KN3 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author:
Tester: Jingbo Shang
Editorialist: Jingbo Shang

DIFFICULTY:

Simple

PREREQUISITES:

Array

PROBLEM:

A string S is repeated P times and its characters are sorted in the alphabetic order. Find out the Nth character for Q different queries.

EXPLANATION:

It is important to find out that you do not need to construct the repeated string for the queries. As long as you have the number of different characters, you should be able to answer those queries.

Therefore, we can simply use an array to count the occurrences of all characters, i.e. cnt[c] stands for the number of occurrences of character c in the repeated string. To answer the queries, one can go through the cnt array in the alphabetic order and check the occurrence.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

2

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX 100001
typedef long long int ll;
ll BIT[MAX];
void update(ll n,ll val,ll N)
{
for(;n<=N;BIT[n]+=val,n+=n&-n);
}
ll read(ll n)
{
ll sum=0;
for(;n;sum+=BIT[n],n-=n&-n);
return sum;
}
int main()
{
ll t;
scanf("%lld",&t);

while(t--)
{
    memset(BIT,0,sizeof BIT);
    ll n,c;
    scanf("%lld %lld",&n,&c);
    ll ch,p,q,v;
    while(c--){
    scanf("%lld",&ch);
    if(ch==0)
    {
        scanf("%lld %lld %lld",&p,&q,&v);
        for(ll k=p;k<=q;k++)
        {
            update(k,v,n); // Passing Size of Array as well So as to Not Iterate Through all 10001 All
        }

    }
    else
    {
        scanf("%lld %lld",&p,&q);
        printf("%lld",read(q)-read(p-1));// Return Sum of Range From p to q
    }
    }
}

}**