Sequence Master MASTER Solution Codechef

Sequence Master MASTER Solution

Given is a sequence A of length N. Define f(i,j) to be the number of distinct elements in Ai,Ai+1,…,Aj. You need to process Q queries of the following two types:

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

Input Format

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

Output Format

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

Constraints

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

Subtasks

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

Sample Input 1

3 2
1 2 2
2 2
2 3

Sample Output 1

4
8

Explanation

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

Test Case 2: 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=8.

Sample Input 2

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

Sample Output 2

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];
    void add(int x,ll v){for(;x<=n;x+=(x&-x)) a[x]+=v;}
    ll qry(int x){ll v=0;for(;x;x-=(x&-x)) v+=a[x];return v;}
}t1,t2;
void add(int i,int v){t1.add(i,v);t2.add(i,1ll*(i-1)*v);}
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())
    {
        add(*p,-((*p)-(*q)));
        add(*p,(*p)-i);
    }
    add(i,i-(*q));
    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())
    {
        add(*p,-((*p)-i));
        add(*p,(*p)-(*q));
    }
    add(i,-(i-(*q)));
}
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++)
    {
        add(i,i-(*f[a[i]].rbegin()));
        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);
		}
		return total;
	}
	
	static void rangeAdd(int l, int r, long x) {
		add(b1, l, x);
		add(b1, r+1, -x);
		add(b2, l, x*(l-1));
		add(b2, r+1, -x*r);
	}
	
	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 {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		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++) {
			st = new StringTokenizer(br.readLine());
			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++)
			tmaps.add(new TreeMap<Integer,Integer>());
		
		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++)
			rangeAdd(i, n, i - previous[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];
				rangeAdd(x,next[x]-1,-(x-previous[x]));
				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;
				
				rangeAdd(x,next[x]-1,x-previous[x]);
				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)

January Long Challenge 2022 Solution

Leave a Comment

2 + 19 =