# Sequence Master MASTER Solution Codechef

Page Contents

## Codechef Sequence Master MASTER Solution

Given is a sequence AA of length NN.

Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,…,AjAi,Ai+1,…,Aj.

You need to process QQ queries of the following two types:

• 1 x y1 x y — set Ax=yAx=y.
• 2 k2 k — print ∑i=1k∑j=ikf(i,j)∑i=1k∑j=ikf(i,j).

### Input Format

• The first line of input contains two integers NN and QQ — the size of the array and the number of queries.
• The second line of input contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• Then, QQ lines follow, describing queries in the format given in the statement.

### Output Format

For each type 22 query, print the answer to it on a new line.

### Constraints

• 1≤N,Q≤2⋅1051≤N,Q≤2⋅105
• 1≤Ai≤N1≤Ai≤N
• 1≤x,y≤N1≤x,y≤N
• 1≤k≤N1≤k≤N

• Subtask 1 (20 points): No type 11 queries
• Subtask 2 (80 points): Original constraints

```3 2
1 2 2
2 2
2 3```

```4
8```

### Explanation

Test Case 11: The answer is f(1,1)+f(1,2)+f(2,2)=1+2+1=4f(1,1)+f(1,2)+f(2,2)=1+2+1=4.

Test Case 22: The answer is f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8.

```5 5
1 2 3 4 5
2 5
1 1 2
2 3
2 4
2 5```

```35
8
17
31```

## Solution

Program: Sequence Master MASTER Solution in C++

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#define N 200010
#define ll long long
using namespace std;
int a[N],n;
set<int>f[N];
struct ta{
ll a[N];
ll qry(int x){ll v=0;for(;x;x-=(x&-x)) v+=a[x];return v;}
}t1,t2;
ll qry(int k){return 1ll*k*t1.qry(k)-t2.qry(k);}
void insert(int i,int x)
{
auto p=f[x].lower_bound(i),q=prev(p);
if(p!=f[x].end())
{
}
f[x].insert(i);
}
void erase(int i,int x)
{
f[x].erase(i);
auto p=f[x].lower_bound(i),q=prev(p);
if(p!=f[x].end())
{
}
}
int main()
{
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i].insert(0);
for(int i=1;i<=n;i++)
{
f[a[i]].insert(i);
}
for(int i=1;i<=m;i++)
{
int op,x,y;scanf("%d%d",&op,&x);
if(op==1)
{
scanf("%d",&y);
erase(x,a[x]);
a[x]=y;
insert(x,a[x]);
}
else printf("%lld\n",qry(x));
}
return 0;
}```

Program: Sequence Master MASTER Solution in Java

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {

static int n;
static long[] b1;
static long[] b2;

static void add(long[] b, int x, long val) {
int i = x;
while(i <= n) {
b[i] += val;
i += i & (-i);
}
}

static long sum(long[] b, int x) {
long total = 0;
int i = x;
while(i > 0) {
total += b[i];
i -= i & (-i);
}
}

static void rangeAdd(int l, int r, long x) {
}

static long prefixSum(int x) {
return (sum(b1, x)*x) - sum(b2, x);
}

static long rangeSum(int l, int r) {
return prefixSum(r) - prefixSum(l-1);
}

public static void main(String[] args) throws IOException {

PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

int[] a = new int[n+1];

for(int i = 1; i <= n; i++)
a[i] = Integer.parseInt(st.nextToken());

int[][] queries = new int[q][3];

for(int i = 0; i < q; i++) {
queries[i][0] = Integer.parseInt(st.nextToken());
if(queries[i][0] == 1) {
queries[i][1] = Integer.parseInt(st.nextToken());
queries[i][2] = Integer.parseInt(st.nextToken());
} else {
queries[i][1] = Integer.parseInt(st.nextToken());
}
}

int[] next = new int[n+2];
int[] previous = new int[n+2];
Arrays.fill(next, n+1);

int[] lastOfType = new int[n+1];
Arrays.fill(lastOfType, 0);

ArrayList<TreeMap<Integer,Integer>> tmaps = new ArrayList<TreeMap<Integer,Integer>>();

for(int i = 0; i <= n; i++)

for(int i = 1; i <= n; i++) {
previous[i] = lastOfType[a[i]];
next[previous[i]] = i;
lastOfType[a[i]] = i;
tmaps.get(a[i]).put(i,i);
}

b1 = new long[n+1];
b2 = new long[n+1];

for(int i = 1; i <= n; i++)

for(int i = 0; i < q; i++) {
if(queries[i][0] == 2) {
pw.println(rangeSum(1, queries[i][1]));
} else {
int x = queries[i][1]; int y = queries[i][2];
next[previous[x]] = next[x];
previous[next[x]] = previous[x];
tmaps.get(a[x]).remove(x);

Integer newPrevious = tmaps.get(y).lowerKey(x);
Integer newNext = tmaps.get(y).higherKey(x);

previous[x] = newPrevious == null ? 0 : newPrevious;
next[x] = newNext == null ? n+1 : newNext;

next[newPrevious == null ? 0 : newPrevious] = x;
previous[newNext == null ? n+1 : newNext] = x;

a[x] = y;

tmaps.get(y).put(x,x);
}
}

pw.close();

}

}```

Program: Sequence Master MASTER Solution in Python

```def getsum(a):
news = [1]
freq = {a[0]:0}
shinsu=1
last=1
for i in range(1,len(a)):
shinsu = news[i-1] + 1
shinsu += last + i
if(a[i] in freq):
shinsu -= freq[a[i]]+1

freq[a[i]] = i
last = shinsu - news[i-1]
news.append(shinsu)
return(news)

c,d = map(int,input().split())
a = list(map(int,input().split()))

sumlist = getsum(a)

for _ in range(d):
querie = list(map(int,input().split()))
if(querie[0]==2):
#print(sumlist)
print(sumlist[querie[1]-1])
else:
a[querie[1]-1] = querie[2]
sumlist = getsum(a)```