- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
这是我要解决的问题,我正在使用 The Fact That Prefix Sum[i] - Prefix Sum[i-1]
Leads to Frequency being greater than zero 来识别不同的数字和然后我正在消除频率,但即使使用 BIT,我也会得到 TLE
给定一个由 n 个数字 a1、a2、...、an 和许多 d 查询组成的序列。
d-query 是一对 (i, j) (1 ≤ i ≤ j ≤ n)。
对于每个 d 查询 (i, j),您必须返回子序列 ai, ai+1, ..., aj 中不同元素的数量。
Input
Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j
representing a d-query (1 ≤ i ≤ j ≤ n).
Output
For each d-query (i, j), print the number of distinct elements in the
subsequence ai, ai+1, ..., aj in a single line.
Example
Input
5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
代码是:
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
typedef long long int ll;
using namespace std;
void update(ll n, ll val, vector<ll> &b);
ll read(ll n,vector<ll> &b);
ll readsingle(ll n,vector<ll> &b);
void map(vector<ll> &a,vector<ll> &b,ll n) /**** RElative Mapping ***/
{
ll temp;
a.clear();
b.clear();
for(ll i=0; i<n; i++)
{
cin>>temp;
a.push_back(temp);
b.push_back(temp);
}
sort(b.begin(),b.end());
for(ll i=0; i<n; i++)
*(a.begin()+i) = (lower_bound(b.begin(),b.end(),a[i])-b.begin())+1;
b.assign(n+1,0);
}
int main()
{
ll n;
cin>>n;
vector<ll> a,b;
map(a,b,n);
ll t;
cin>>t;
while(t--)
{
ll l ,u;
b.assign(n+1,0);
cin>>l>>u;
l--;/*** Reduce For Zero Based INdex ****/
u--;
for(ll i=l;i<=u;i++)
update(a[i],1,b);
ll cont=0;
for(ll i=l;i<=u;i++)
if(readsingle(a[i],b)>0)
{
cont++;
update(a[i],-readsingle(a[i],b),b); /***Eliminate The Frequency */
}
cout<<cont<<endl;
}
return 0;
}
ll readsingle(ll n,vector<ll> &b)
{
return read(n,b)-read(n-1,b);
}
ll read(ll n,vector<ll> &b)
{
ll sum=0;
for(; n; sum+=b[n],n-=n&-n);
return sum;
}
void update(ll n, ll val, vector<ll> &b)
{
for(; n<=b.size(); b[n]+=val,n+=n&-n);
}
最佳答案
您使用的算法太慢了。对于每个查询,您遍历整个查询范围,这已经给出了 n * q
操作(显然,这太多了)。这是一个更好的解决方案(它具有 O((n + q) * log n)
时间和 O(n + q)
空间复杂度(它是一个离线解决方案) :
让我们按右端对所有查询进行排序(无需明确对它们进行排序,您只需将查询添加到适当的位置(从 0
到 n - 1
)).
现在让我们从左到右遍历数组中的所有位置并维护一个 BIT。 BIT中的每个位置要么是1
(这意味着在位置i
处有一个新元素)要么是0
(最初,它被填充带零)。
对于每个元素a[i]
:如果它是该元素的第一次出现,只需在BIT 中的i
位置加一个。否则,将-1
添加到该元素上一次出现的位置,然后将1
添加到i
位置。
查询(left, right)
的答案只是从left
到right
的所有元素的总和。
要维护每个元素的最后一次出现,您可以使用 map 。
可以使用持久线段树使其在线(时间复杂度是相同的,相同的复杂度将变为O(n * log n + q)
),但它不是这里需要。
关于algorithm - SPOJ DQUERY : TLE Even With BIT?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27656135/
这是我要解决的问题,我正在使用 The Fact That Prefix Sum[i] - Prefix Sum[i-1] Leads to Frequency being greater than
我有 2 个实体:具有多对一关系的 teacher、subject (科目很多---一名老师),它为我创建了第三个表subject_teacher 我有一个用于创建教师的表单和一个用于创建主题的表单,
我是一名优秀的程序员,十分优秀!