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 3Sample Output 1
4
8Explanation
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 5Sample Output 2
35
8
17
31SOLUTION
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)