HDU 4638 多校第四场1007 离线询问，树状数组||线段树维护 - c++编程基础

+ ; } ans[ed[i].id] = sum(ed[i].e) - sum(ed[i].s - 1) ; } for (int i = 0 ; i < m ; i ++ ){ printf("%d\n",ans[i]) ; } } return 0 ; } #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define Max 2505 #define inf 1<<28 #define LL(x) ( x << 1 ) #define RR(x) ( x << 1 | 1 ) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define PII pair using namespace std; inline void RD(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } inline void OT(int a){ if(a >= 10)OT(a / 10) ; putchar(a % 10 + '0') ; } #define N 100005 int a[N] ; int n , m ; struct kdq{ int s , e , id ; }ed[N] ; bool cmp(const kdq& a ,const kdq& b){ return a.s < b.s ; } int c[N] ; inline void update(int pos ,int num){ for (int i = pos ; i <= n ; i += i & (-i) ){ c[i] += num ; } } inline int sum(int pos){ int ans = 0 ; for (int i = pos ; i >

= 1 ; i -= i & (-i)){ ans += c[i] ; } return ans ; } int is[N] ; int ans[N] ; int pos[N] ; int main() { int T ; cin >> T ; while( T -- ){ cin >> n >> m ; mem(c ,0) ; mem(is , 0) ; mem(pos , 0) ; REP(i , 1 , n ){ RD(a[i]) ; pos[a[i]] = i ; } REP(i , 0 , m - 1){ RD(ed[i].s) ; RD(ed[i].e) ; ed[i].id = i ; } REP(i , 1 , n){ int nn = 0 ; if(is[a[i] + 1])nn ++ ; if(is[a[i] - 1])nn ++ ; if(nn == 2)update(i , -1) ; else if(nn == 0)update(i , 1) ; is[a[i]] = 1 ; } sort(ed , ed + m ,cmp) ; int st = 1 ; for (int i = 0 ; i < m ; i ++ ){ while(ed[i].s > st){ if(pos[a[st] + 1] > st && a[st] < n){ update(pos[a[st] + 1] , 1) ; } if(pos[a[st] - 1] > st && a[st] > 1){ update(pos[a[st] - 1] , 1) ; } st ++ ; } ans[ed[i].id] = sum(ed[i].e) - sum(ed[i].s - 1) ; } for (int i = 0 ; i < m ; i ++ ){ printf("%d\n",ans[i]) ; } } return 0 ; }

HDU 4638 多校第四场1007 离线询问，树状数组||线段树维护 (二)