hdu 4638 Group
离线处理+树状数组
//http://blog.csdn.net/zz_1215/ #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<queue> #include<stack> #include<string> #include<map> #include<set> #include<cmath> #include<cassert> #include<cstring> #include<iomanip> #include<ctime> using namespace std; typedef long long i64; #define S64(a) scanf(in64,&a) #define SS(a) scanf("%d",&a) #define LL(a) ((a)<<1) #define RR(a) (((a)<<1)+1) #define pb push_back #define pf push_front #define X first #define Y second #define CL(Q) while(!Q.empty())Q.pop() #define MM(name,what) memset(name,what,sizeof(name)) #define MC(a,b) memcpy(a,b,sizeof(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?
(a):(b)) #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout) const int inf = 0x3f3f3f3f; const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL; const double oo = 10e9; const double eps = 10e-9; const double pi = acos(-1.0); const int maxn = 100000 + 111; struct zz{ int l, r, id; bool operator < (const zz& cmp) const{ return l < cmp.l; } }; int n, m; int a[maxn]; bool have[maxn]; int pos[maxn]; int ta[maxn]; int ans[maxn]; vector<zz>v; int lowbit(int x){ return x & (-x); } void add(int pos, int num, int ary[]){ while (pos <= n){ ary[pos] += num; pos += lowbit(pos); } } int sum(int x, int ary[]){ // 1 to x int ans = 0; while (x){ ans += ary[x]; x -= lowbit(x); } return ans; } int query(int x, int y){ return sum(y, ta) - sum(x - 1, ta); } inline int find(int x){ if (!have[x - 1] && !have[x + 1]){ return 1; } else if (have[x - 1] && have[x + 1]){ return -1; } else{ return 0; } } void start(){ for (int i = 1; i <= n; i++){ have[i] = false; ta[i] = 0; } for (int i = 1; i <= n; i++){ pos[a[i]] = i; } for (int i = 1; i <= n; i++){ add(i, find(a[i]), ta); have[a[i]] = true; } int temp = 0; for (int i = 1; i <= n; i++){ while (temp <(int) v.size()){ if (v[temp].l == i){ ans[v[temp].id] = query(v[temp].l, v[temp].r); temp++; } else{ break; } } have[a[i]] = false; if (have[a[i] + 1]){ add(pos[a[i] + 1], 1, ta); } if (have[a[i] - 1]){ add(pos[a[i] - 1], 1, ta); } } return; } int main() { int T; cin >> T; while (T--){ cin >> n >> m; for (int i = 1; i <= n; i++){ cin >> a[i]; } zz temp; v.clear(); for (int i = 1; i <= m; i++){ //cin >> temp.l >> temp.r; SS(temp.l); SS(temp.r); temp.id = i; v.push_back(temp); } sort(v.begin(), v.end()); start(); for (int i = 1; i <= m; i++){ //cout << ans[i] << endl; printf("%d\n", ans[i]); } } return 0; }
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】
- ORA-01224: group number in header string does not match GROUP string ORACLE 报错 故障修复 远程处理
- ORA-01224: group number in header string does not match GROUP string ORACLE 报错 故障修复 远程处理
- by的使用利用Oracle中Group By实现数据汇总(oracle中group)
- by和having的用法详解,协助你更好地使用MySQL的Group by函数(mysql 中group)
- MySQL 三表 Group 查询实现精细数据分析(mysql三表group)