[hdu5200]离线+标记-白红宇

[hdu5200]离线+标记

阅读量：4617 次

发布时间：2019-06-09

本文共 2840 字，大约阅读时间需要 9 分钟。

思路：按顺序处理，新建一堆然后向左右合并，不过巧妙地用了标记数组来记录和统计答案。

1 #pragma comment(linker, "/STACK:10240000,10240000")  2   3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
             8 #include 
            9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 using namespace std; 18 19 #define mem0(a) memset(a, 0, sizeof(a)) 20 #define lson l, m, rt << 1 21 #define rson m + 1, r, rt << 1 | 1 22 #define define_m int m = (l + r) >> 1 23 #define rep(a, b) for(int a = 0; a < b; a++) 24 #define all(a) (a).begin(), (a).end() 25 #define lowbit(x) ((x) & (-(x))) 26 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {} 27 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 28 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 29 #define pc(a) putchar(a) 30 #define ps(a) puts(a) 31 32 typedef double db; 33 typedef long long LL; 34 typedef pair
                   
                     pii; 35 typedef multiset
                    
                      msi; 36 typedef multiset
                     
                      ::iterator msii; 37 typedef set
                      
                        si; 38 typedef set
                       
                        ::iterator sii; 39 typedef vector
                        
                          vi; 40 41 const int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1}; 42 const int dy[8] = { 0, -1, 0, 1, -1, 1, 1, -1}; 43 const int maxn = 1e6 + 7; 44 const int maxm = 1e5 + 7; 45 const int maxv = 1e7 + 7; 46 const int max_val = 1e6 + 7; 47 const int MD = 1e9 +7; 48 const int INF = 1e9 + 7; 49 const double PI = acos(-1.0); 50 const double eps = 1e-10; 51 52 inline int ReadInt() { 53 char c = getchar(); 54 while(!isdigit(c)) c = getchar(); 55 56 int x = 0; 57 while(isdigit(c)) { 58 x = x * 10 + c - '0'; 59 c = getchar(); 60 } 61 return x; 62 } 63 64 inline void WriteInt(int i) { 65 int p = 0; 66 static int buf[10]; 67 if(i == 0) buf[p++] = 0; 68 else while(i) { 69 buf[p++] = i % 10; 70 i /= 10; 71 } 72 for(int j = p - 1; j >= 0; j--) putchar('0' + buf[j]); 73 } 74 75 76 bool cmp(const pii &a, const pii &b) { 77 return a.first > b.first; 78 } 79 80 int main() { 81 //freopen("in.txt", "r", stdin); 82 int n, q; 83 while (cin >> n >> q) { 84 vector
                         
                           a(n), b(q); 85 vector
                          
                            out(q); 86 rep(i, n) { 87 a[i].first = ReadInt(); 88 a[i].second = i; 89 } 90 rep(i, q) { 91 b[i].first = ReadInt(); 92 b[i].second = i; 93 } 94 sort(all(a), cmp); 95 sort(all(b), cmp); 96 vector
                           
                             vis(n); 97 int now = 0, ans = 0; 98 rep(i, q) { 99 while (now < n && a[now].first > b[i].first) {100 int pos = a[now].second;101 vis[pos] = true;102 ans++;103 if (pos && vis[pos - 1]) ans--;104 if (pos < n - 1 && vis[pos + 1]) ans--;105 now++;106 }107 out[b[i].second] = ans;108 }109 rep(i, q) {110 WriteInt(out[i]);111 pc('\n');112 }113 }114 return 0;115 }