CM1906-Editorial

PROBLEM LINK:

Practice
Contest

Author: sumit
Tester: Neeraj
Editorialist: Manish

DIFFICULTY:

EASY.

PREREQUISITES:

Math, SegmentTree.

PROBLEM:

Mayank and Rachit are best friends. They both are good programmers as well. They love programming together because if one of them gets stuck on some problems other can help. But these days Mayank is quite busy as his exams are approaching. So, Rachit has to tackle the problems alone. While practicing Rachit encounters an interesting problem which he was unable to solve efficiently. So, he asked Mayank for help. Problem as stated by Rachit : Given an array of N elements, Q queries need to be processed over this array. A query can be of any of the following three types:

Type 0: u v

Type 1: u v

Type 2: l r c

EXPLANATION:

This questions depends on understanding Data Structure, such as Segment Trees

or Binary Indexed Trees.

I will solve this question using Segment Trees.

Firstly: You should build a segment tree but for all the possible

distinct number of digits: tree[index][10] as every index in the tree

will contain how many numbers have distinct digits i such that

.

You should initialize every leaf index in the tree by putting the number

of distinct digits in this number as 1, tree[index][i] = 1, and all other

are set to zero.

After you calculate tree[index] for all leaves, you should sum the left and

right sides and gather the summation in a tree index:

for(int i = 1; i <= 10; i++){

tree[index][i] = tree[index * 2 + 1][i] + tree[index * 2 + 2][i];

}

Secondly: In update queries, you should update the wanted index in the array

and run the same algorithm to update the corresponding tree leaf, then updating

the whole tree.

Thirdly: In third types of queries, you can call a query method which traverse the

tree to find the required interval, then output the required number of numbers which

have distinct digits © in the given interval.

Note: Naive for loops solution will result in Time Limit Exceeded.

Time Complexity:

.

Note:

for building the tree,

for each query.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int dig(ll n)
{
int arr[10]={0};
int x;
while(n>0)
{
x=n%10;
arr[x]++;
n/=10;
}
int ans=0;
for(int i=0;i<10;i++)
if(arr[i]!=0)
ans++;
return ans;
}
int main()
{
ll n;
cin>>n;
ll arr[n];
ll sz=n+1;
for(int i=0;i<n;i++)
cin>>arr[i];
ll bit[11][n+1];
memset(bit,0,sizeof(bit));
for(int i=0;i<n;i++)
{
int idx=i+1;
int p=dig(arr[i]);
while(idx<=sz)
{
bit[p][idx]++;
idx+=(idx & -idx);
}
}
ll q;
cin>>q;
ll a,u,v,c;
while(q–)
{
cin>>a;
if(a==0)
{
cin>>u>>v;
int u1=u;
int p=dig(arr[u-1]);
while(u<=sz)
{
bit[p][u]–;
u+=(u & -u);
}
arr[u1-1]+=v;
p=dig(arr[u1-1]);
while(u1<=sz)
{
bit[p][u1]++;
u1+=(u1 & -u1);
}
}
else if(a==1)
{
cin>>u>>v;
int u1=u;
int p=dig(arr[u-1]);
while(u<=sz)
{
bit[p][u]–;
u+=(u & -u);
}
arr[u1-1]=v;
p=dig(arr[u1-1]);
while(u1<=sz)
{
bit[p][u1]++;
u1+=(u1 & -u1);
}
}
else
{
cin>>u>>v>>c;
ll sum=0;
while(v>0)
{
sum+=bit[c][v];
v-=(v & -v);
}
u–;
while(u>0)
{
sum-=bit[c][u];
u-=(u & -u);
}
cout<<sum<<"\n";
}
}
return 0;
}

Tester's Solution

indent whole code by 4 spaces

Editorialist's Solution

indent whole code by 4 spaces