連結：戳這裡
C. Little Artem and Random Variable time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Little Artyom decided to study probability theory. He found a book with a lot of nice exercises and now wants you to help him with one of them.
Consider two dices. When thrown each dice shows some integer from 1 to n inclusive. For each dice the probability of each outcome is given (of course, their sum is 1), and different dices may have different probability distributions.
We throw both dices simultaneously and then calculate values max(a, b) and min(a, b), where a is equal to the outcome of the first dice, while b is equal to the outcome of the second dice. You don't know the probability distributions for particular values on each dice, but you know the probability distributions for max(a, b) and min(a, b). That is, for each x from 1 to n you know the probability that max(a, b) would be equal to x and the probability that min(a, b) would be equal to x. Find any valid probability distribution for values on the dices. It's guaranteed that the input data is consistent, that is, at least one solution exists.
Input
First line contains the integer n (1 ≤ n ≤ 100 000) — the number of different values for both dices.
Second line contains an array consisting of n real values with up to 8 digits after the decimal point — probability distribution for max(a, b), the i-th of these values equals to the probability that max(a, b) = i. It's guaranteed that the sum of these values for one dice is 1. The third line contains the description of the distribution min(a, b) in the same format.
Output
Output two descriptions of the probability distribution for a on the first line and for b on the second line.
The answer will be considered correct if each value of max(a, b) and min(a, b) probability distribution values does not differ by more than 1e-6 from ones given in input. Also, probabilities should be non-negative and their sums should differ from 1 by no more than 1e-6.
Examples
input
2
0.25 0.75
0.75 0.25
output
0.5 0.5
0.5 0.5
input
3
0.125 0.25 0.625
0.625 0.25 0.125
output
0.25 0.25 0.5
0.5 0.25 0.25
題意：分别給出P( max(a,b)=i ) 和 P( min(a,b)=i ) 的機率,要求出P(a=i) 和 P(b=i) 的機率
思路：
P(a = i) == P(a <= i) - P(a <= i-1)
P(max(a, b) <= i) == P(a <= i) * P(b <= i)
P(min(a, b) >= i+1) == P(a >= i+1) * P(b >= i+1) = (1 - P(a <= i)) *(1 - P(b <= i))
=> P(max(a,b)<=i)=P(a<=i) * P(b<=i)
P(min(a,b)<=i+1)=(1-P(a<=i)) * (1-P(b<=i))
解方程的 P(a<=i) 和 P(b<=i) , 進而求得P(a=i)和P(b=i)
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n;
double a[100100],b[100100];
double sum1[100100],sum2[100100];
double anw1[100100],anw2[100100];
const double eps=1e-10;
int dcmp(double x){
if(fabs(x)<=eps) return 0;
return x<0?-1:1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%lf",&a[i]);
sum1[i]=sum1[i-1]+a[i];
}
for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
for(int i=n;i>=1;i--) sum2[i]=sum2[i+1]+b[i];
for(int i=1;i<=n;i++){
double a=sum1[i],b=sum2[i+1],deta;
b=a-b+1.0;
deta=sqrt(max(b*b-4.0*a,0.0));
anw1[i]=(b-deta)*0.5;
anw2[i]=(b+deta)*0.5;
}
for(int i=1;i<=n;i++) printf("%.10f ",anw1[i]-anw1[i-1]);
cout<<endl;
for(int i=1;i<=n;i++) printf("%.10f ",anw2[i]-anw2[i-1]);
cout<<endl;
return 0;
}<strong>
</strong>
E. Little Artem and Time Machine time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Little Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: multiset.
Artem wants to create a basic multiset of integers. He wants these structure to support operations of three types:
Add integer to the multiset. Note that the difference between set and multiset is that multiset may store several instances of one integer.
Remove integer from the multiset. Only one instance of this integer is removed. Artem doesn't want to handle any exceptions, so he assumes that every time remove operation is called, that integer is presented in the multiset.
Count the number of instances of the given integer that are stored in the multiset.
But what about time machine? Artem doesn't simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.
First Artem adds integer 5 to the multiset at the 1-st moment of time.
Then Artem adds integer 3 to the multiset at the moment 5.
Then Artem asks how many 5 are there in the multiset at moment 6. The answer is 1.
Then Artem returns back in time and asks how many integers 3 are there in the set at moment 4. Since 3 was added only at moment 5, the number of integers 3 at moment 4 equals to 0.
Then Artem goes back in time again and removes 5 from the multiset at moment 3.
Finally Artyom asks at moment 7 how many integers 5 are there in the set. The result is 0, since we have removed 5 at the moment 3.
Note that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.
Help Artem implement time travellers multiset.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of Artem's queries.
Then follow n lines with queries descriptions. Each of them contains three integers ai, ti and xi (1 ≤ ai ≤ 3, 1 ≤ ti, xi ≤ 109) — type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It's guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.
Output
For each ask operation output the number of instances of integer being queried at the given moment of time.
Examples
input
6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5
output
1
2
1
input
3
1 1 1
2 2 1
3 3 1
output
題意：
給出三個操作 a,t,x
a=1：在位于時間軸t處加入一個權值x
a=2：在位于時間軸t處删除一個權值x
a=3：在位于時間軸t處之前出現了多少次x
時間軸的含義就是 隻對時間t之前的操作有效
思路：
由于時間的範圍是(1<=t<=1e9) ,但是這裡提到了一點就是時間軸 顯然每個時間隻會出現一次
但是操作隻有n個(1<=n<=1e5) 這裡可以離散化一下就把時間縮成(1e5)
接着就是在該時間點加入值或者删除值,直接用map标記處理出來logn
但是還有一個詢問要求詢問一段區間内的x的個數,顯然直接套個樹狀數組就可以了
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n;
struct node{
int id,a,t,x;
}s[100100];
bool cmp(node a,node b){
return a.t<b.t;
}
bool cmp1(node a,node b){
return a.id<b.id;
}
map<int ,int > mp[100100];
int lowbit(int x){
return x&(-x);
}
void Add(int x,int v,int num){
while(x<=n){
mp[x][v]+=num;
x+=lowbit(x);
}
}
int query(int x,int v){
int ans=0;
while(x>=1){
ans+=mp[x][v];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d%d",&s[i].a,&s[i].t,&s[i].x);
s[i].id=i;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++) s[i].t=i;
sort(s+1,s+n+1,cmp1);
//for(int i=1;i<=n;i++) cout<<s[i].a<<" "<<s[i].t<<" "<<s[i].x<<endl;
for(int i=1;i<=n;i++){
if(s[i].a==1) Add(s[i].t,s[i].x,1);
else if(s[i].a==2) Add(s[i].t,s[i].x,-1);
else printf("%d\n",query(s[i].t,s[i].x));
}
return 0;
}