At the children’s day, the child came to Picks’s house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.
Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1],a[2],...,a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:
Print operation l,r. Picks should write down the value of ∑i=lra[i].
Modulo operation l, r, x. Picks should perform assignment a[i]=a[i]modx for each i (l≤i≤r).
Set operation k,x. Picks should set the value of a[k] to x (in other words perform an assignment a[k]=x).
Can you help Picks to perform the whole sequence of operations?
Input
The first line of input contains two integer: n,m(1≤n,m≤105). The second line contains n integers, separated by space: a[1],a[2],...,a[n](1≤a[i]≤109) — initial value of array elements.
Each of the next m lines begins with a number type(type∈{1,2,3}).
If type=1, there will be two integers more in the line: l,r(1≤l≤r≤n), which correspond the operation 1.
If type=2, there will be three integers more in the line: l,r,x(1≤l≤r≤n;1≤x≤109), which correspond the operation 2.
If type=3, there will be two integers more in the line: k,x(1≤k≤n;1≤x≤109), which correspond the operation 3.
Output
For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.
Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.
There are n planets in their universe numbered from 1 to n. Rick is in planet number s (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.
By default he can not open any portal by this gun. There are q plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.
Plans on the website have three types:
With a plan of this type you can open a portal from planet v to planet u.
With a plan of this type you can open a portal from planet v to any planet with index in range [l,r].
With a plan of this type you can open a portal from any planet with index in range [l,r] to planet v.
Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.
Input
The first line of input contains three integers n, q and s(1≤n,q≤105,1≤s≤n) — number of planets, number of plans and index of earth respectively.
The next q lines contain the plans. Each line starts with a number t, type of that plan (1≤t≤3). If t=1 then it is followed by three integers v, u and w where w is the cost of that plan (1≤v,u≤n,1≤w≤109). Otherwise it is followed by four integers v, l, r and w where w is the cost of that plan (1≤v≤n,1≤l≤r≤n,1≤w≤109).
Output
In the first and only line of output print n integers separated by spaces. i-th of them should be minimum money to get from earth to i-th planet, or −1 if it’s impossible to get to that planet.
Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated n Mr. Meeseeks, standing in a line numbered from 1 to n. Each of them has his own color. i-th Mr. Meeseeks’ color is ai.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most k different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each 1≤i≤e≤j≤n, if Mr. Meeseeks number i and Mr. Meeseeks number j are in the same squad then Mr. Meeseeks number e should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of k, so in order to choose it, for each k between 1 and n (inclusive) need to know the minimum number of presidios needed.
Input
The first line of input contains a single integer n(1≤n≤105) — number of Mr. Meeseeks.
The second line contains n integers a1,a2,...,an separated by spaces (1≤ai≤n) — colors of Mr. Meeseeks in order they standing in a line.
Output
In the first and only line of input print n integers separated by spaces. i-th integer should be the minimum number of presidios needed if the value of k is i.
Examples
1 2
5 1 3 4 3 3
1
4 2 1 1 1
1 2
8 1 5 7 8 1 7 6 1
1
8 4 3 2 1 1 1 1
Note
For the first sample testcase, some optimal ways of dividing army into squads for each k are:
[1],[3],[4],[3,3]
[1],[3,4,3,3]
[1,3,4,3,3]
[1,3,4,3,3]
[1,3,4,3,3]
For the second testcase, some optimal ways of dividing army into squads for each k are:
intbuild(int s, int t) { int rt = tot++; tree[rt].l = s; tree[rt].r = t; tree[rt].val = 0; if (s == t) return rt; int mid = (s + t) >> 1; tree[rt].lson = build(s, mid); tree[rt].rson = build(mid + 1, t); return rt; }
单点修改
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intupdate(int p, int k, int v) { int rt = tot++; tree[rt] = tree[p]; tree[rt].val += v; if (tree[rt].r == tree[rt].l) return rt; int mid = (tree[rt].l + tree[rt].r) >> 1; if (k <= mid) tree[rt].lson = update(tree[rt].lson, k, v); else tree[rt].rson = update(tree[rt].rson, k, v); return rt; }
查询区间第k小值
1 2 3 4 5 6 7 8 9
intquery(int p, int k)// k-th small { if (tree[p].l == tree[p].r) return tree[p].l; if (k <= tree[tree[p].lson].val) returnquery(tree[p].lson, k); else returnquery(tree[p].rson, k - tree[tree[p].lson].val); }
Give you a sequence and ask you the kth big number of a inteval.
Input
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m(n,m≤100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s,t] indicates the interval and k indicates the kth big number in interval [s,t]
Output
For each test case, output m lines. Each line contains the kth big number.
Tired of playing computer games, alpc23 is planning to play a game on numbers. Because plus and subtraction is too easy for this gay, he wants to do some multiplication in a number sequence. After playing it a few times, he has found it is also too boring. So he plan to do a more challenge job: he wants to change several numbers in this sequence and also work out the multiplication of all the number in a subsequence of the whole sequence.
To be a friend of this gay, you have been invented by him to play this interesting game with him. Of course, you need to work out the answers faster than him to get a free lunch, He he…
Input
The first line is the number of case T(T<=10).
For each test case, the first line is the length of sequence n(n<=50000), the second line has n numbers, they are the initial n numbers of the sequence a1,a2,…,an
Then the third line is the number of operation q(q≤50000), from the fourth line to the q+3 line are the description of the q operations. They are the one of the two forms:
0 k1k2; you need to work out the multiplication of the subsequence from k1 to k2, inclusive. (1≤k1≤k2≤n)
1 kp; the kth number of the sequence has been change to p.(1≤k≤n)
You can assume that all the numbers before and after the replacement are no larger than 1 million.
Output
For each of the first operation, you need to output the answer of multiplication in each line, because the answer can be very large, so can only output the answer after mod1000000007.
To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we’ll give you a chance, to implement the logic behind the scene.
You‘ve been given N integers A[1],A[2],...,A[N]. On these integers, you need to implement the following operations:
Clrd: Adding a constant d for every {Ai∣l≤i≤r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
Qlr: Querying the current sum of {Ai∣l≤i≤r}.
Hlrt: Querying a history sum of {Ai∣l≤i≤r} in time t.
Bt: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
..N,M≤105, ∣A[i]∣≤109, 1≤l≤r≤N, ∣d∣≤104.. the system start from time 0, and the first modification is in time 1, t≥0, and won’t introduce you to a future state.
intbuild(int s, int t) { int rt = ++tot; tree[rt].l = s; tree[rt].r = t; tree[rt].lson = tree[rt].rson = tree[rt].add = 0; if (s == t) { tree[rt].sum = a[s]; return rt; } int mid = (s + t) >> 1; tree[rt].lson = build(s, mid); tree[rt].rson = build(mid + 1, t); tree[rt].sum = tree[tree[rt].lson].sum + tree[tree[rt].rson].sum; return rt; }
区间更新操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
intupdate(int p, int s, int t, ll v) { int rt = ++tot; tree[rt] = tree[p]; tree[rt].sum += v * (min(tree[rt].r, t) - max(tree[rt].l, s) + 1); // note: update all the sum on the way if (tree[rt].l >= s && tree[rt].r <= t) { tree[rt].add += v; // note: sum has been updated above, so just update the tag return rt; } int mid = (tree[rt].r + tree[rt].l) >> 1; if (s <= mid) tree[rt].lson = update(tree[rt].lson, s, t, v); if (t > mid) tree[rt].rson = update(tree[rt].rson, s, t, v); // note: sum has been updated above, so don't have to push up return rt; }
沿路更新时，对于父亲节点而言，所加的值只是一部分区间的长度，切勿使用总长度相乘。
区间查询操作
1 2 3 4 5 6 7 8 9 10 11 12 13
ll query(int p, int s, int t) { if (tree[p].l >= s && tree[p].r <= t) return tree[p].sum; int mid = (tree[p].r + tree[p].l) >> 1; ll ans = tree[p].add * (min(tree[p].r, t) - max(tree[p].l, s) + 1); // note: smaller field // sum all the tag on the way if (s <= mid) ans += query(tree[p].lson, s, t); if (t > mid) ans += query(tree[p].rson, s, t); return ans; }
