关键词：
题意：已知有n个人，从第一个人开始每个人被安排在第ai个空座上，有m组询问，问某人所坐的位置。
分析：
1、用树状数组维护空座的个数，方法：
将所有的空座初始化为1，sum（x）则表示从座位1到座位x空座的个数。
2、对于每个人，根据sum(mid)，二分找使sum(mid)大于等于a[i]的最小的mid，即第ai个空座的位置，并将该位置加上-1，则该位置的值变为0，从而不参与空座数的统计。
3、vis[q]即为标号为q的人所坐的位置。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 50000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int vis[MAXN];
int a[MAXN];
int z[MAXN];
int n;
int sum(int x){
int ans = 0;
for(int i = x; i >= 1; i -= lowbit(i)){
ans += z[i];
}
return ans;
}
void add(int x, int value){
for(int i = x; i <= n; i += lowbit(i)){
z[i] += value;
}
}
int solve(int x){
int l = 1, r = n;
while(l < r){
int mid = l + (r - l) / 2;
if(sum(mid) >= x) r = mid;
else l = mid + 1;
}
return r;
}
int main(){
while(scanf("%d", &n) == 1){
memset(vis, 0, sizeof vis);
for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
add(i, 1);
}
for(int i = 1; i <= n; ++i){
vis[i] = solve(a[i]);
add(vis[i], -1);
}
int m;
scanf("%d", &m);
bool flag = true;
while(m--){
int q;
scanf("%d", &q);
if(flag) flag = false;
else printf(" ");
printf("%d", vis[q]);
}
printf("
");
}
return 0;
}
sgu180inversions（树状数组求逆序数）(代码片段)
题目：?思路：先离散化数据然后树状数组搞一下求逆序数。离散化的方法：https://blog.csdn.net/gokou_ruri/article/details/7723378自己对用树状数组求逆序数的理解：输入数据并利用树状数组求出前边比它小和等于它的数据有几个，用输入... 查看详情
树状数组求逆序对
...对的个数。除了用归并排序来求逆序对个数，还可以使用树状数组来求解。树状数组求解的思路：开一个能大小为这些数的最大值的树状数组，并全部置0。从头到尾读入这些数，每读入一个数就更新树状数组，查看它前面比它... 查看详情
hdu2838cowsorting（树状数组+逆序数）
...中的逆序数2、因为数组的长度比較大所以我们能够通过树状数组来统计结果此处须要两个树状数组第一个：记录小于等于某个 查看详情
[树状数组][逆序数]japan(代码片段)
DescriptionJapanplanstowelcometheACMICPCWorldFinalsandalotofroadsmustbebuiltforthevenue.JapanistallislandwithNcitiesontheEastcoastandMcitiesontheWestcoast(M<=1000,N<=1000).Ksuperhighwayswillbebu 查看详情
树状数组求逆序数及变形（个人理解）(代码片段)
树状数组可以省时间而且省空间的求值和修改，相比于线段树来说代码量少，但我感觉树状数组求逆序数的功能更为强大，树状数组 可以利用从当前加入的数到最大全部添加的优势快速... 查看详情
树状数组的进阶运用（stars数星星）
英文原题ProblemDescriptionAstronomersoftenexaminestarmapswherestarsarerepresentedbypointsonaplaneandeachstarhasCartesiancoordinates.Letthelevelofastarbeanamountofthestarsthatarenothigherandnottotherightof 查看详情
求逆序数（树状数组+离散化）
...并重新编号进另一个数组中然后按原顺序1）一点点更新树状数组（由于树状数组的元素主要是一个数组的部分元素的和，在这里由于只关心个数，所以元素和直接统计为个数和）2）一点点求区间和3）把计算的区间和都相加即可... 查看详情
树状数组求逆序数
１逆序数一波：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。... 查看详情
bzoj3333排队计划树状数组+线段树
...改变了以这些数開始的逆序对没有了于是就好办了我们用树状数组统计出以 查看详情
51nod1107（树状数组逆序数）
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107思路：其实就是升级版的逆序数，x坐标当作位置，y坐标当作数值val，只是可能有相等的数，稍作修改即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=... 查看详情
树状数组求逆序数。，。蓝桥杯小朋友排队
先介绍一下树状数组。什么是树状数组呢？树状数组(BinaryIndexedTree(BIT),FenwickTree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在... 查看详情
hdu2838（树状数组求逆序数）
题意：给你N个排列不规则的数（1~N），任务是把它从小到大排好，每次仅仅能交换相邻两个数，交换一次的代价为两数之和。求最小代价思路：对于当前数X。我们如果知道前面比它大的数有多少，如果为K，那么有部分代价是确... 查看详情
求排列的逆序数之树状数组
代码实现#include<iostream>#include<cstdio>#include<cstdlib>usingnamespacestd;intnum[100001];intn,a[100001];longlongcount=0; voidadd(intx){for(inti=x;i<=n;i+=(i&-i))num[i]++;} 查看详情
hdu4911inversion树状数组求逆序数对
显然每次交换都能降低1所以求出逆序数对数，然后-=k就好了。。。_(:зゝ∠)_ #include<stdio.h>#include<string.h>#include<stdlib.h>#include<set>#include<map>#include<iostream>#include<algorithm 查看详情
zoj-2386ultra-quicksort树状数组求逆序数+离散化
DescriptionInthisproblem,youhavetoanalyzeaparticularsortingalgorithm.Thealgorithmprocessesasequenceofndistinctintegersbyswappingtwoadjacentsequenceelementsuntilthesequenceissortedinascendingorder.Fort 查看详情
hdu-3333turingtree离线区间+树状数组（区间不同数的和）(代码片段)
...这样可以从左到右扫一遍，用尺取法一个一个将数字放入树状数组中。如果这个数字已经在树状数组里面，记录之前的下标，再从树状数组中删去之前下标的这个数字，在当前下标添加该数字 查看详情
poj2299ultra-quicksort（树状数组求逆序数+离散化）
题目链接：http://poj.org/problem?id=2299DescriptionInthisproblem,youhavetoanalyzeaparticularsortingalgorithm.Thealgorithmprocessesasequenceofndistinctintegersbyswappingtwoadjacentsequenceelementsuntilthese 查看详情
[树状数组]求排列的逆序数(代码片段)
求排列的逆序数 题目描述 在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评... 查看详情