PROBLEM LINK:
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 (c) 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