HDU 4031 树状数组区间更新及点询问-白红宇

HDU 4031 树状数组区间更新及点询问

阅读量：2440 次

发布时间：2019-05-10

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

/*******************************************************************************    去年成都赛区网络赛一道题，树状数组在区间更新中的应用。树状数组一般支持的是改点，查区间，但是这道题要求的是改区间，查点，这就要变通一下，具体可以看代码，另外要考虑的一个问题是，如何统计？这里的处理方法就是把总共的攻击次数-防御的次数，因为对单个点的询问可能有多次，所以为每个点都设定一个游标来优化时间～*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x) {return x * x;}template 
                                      
                                       T ll(const T & x) {return x << 1;}template 
                                       
                                        T rr(const T & x) {return x << 1 | 1;}template 
                                        
                                         T gcd(T a, T b) { if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 20004;int test, n, q, t;int tree[MAXN];int crs[MAXN], def[MAXN];vector
                                         
                                           vp;void updateBIT(int x, int inc){ for (int i = x; i > 0; i -= LOWBIT(i)) { tree[i] += inc; } return ;}void updateSeg(int l, int r, int inc){ updateBIT(l - 1, -inc); updateBIT(r, inc); return ;}int queryBIT(int x){ int sum = 0; for (int i = x; i <= n; i += LOWBIT(i)) { sum += tree[i]; } return sum;}void ace(){ int cas = 1; char op[10]; int l, r, p; for (scanf("%d", &test); test--; ++cas) { scanf("%d %d %d", &n, &q, &t); CLR(tree, 0); CLR(crs, 0); CLR(def, 0); vp.clear(); int ind = 0; printf("Case %d:\n", cas); while (q--) { scanf("%s", op); if ('A' == op[0]) { scanf("%d %d", &l, &r); if (l > r) { swap(l, r); } //l = max(l, 1); //r = min(r, n); updateSeg(l, r, 1); vp.push_back(PII(l, r)); ++ind; } else { scanf("%d", &p); if (1 == t) { puts("0"); continue ; } int token = 0; while (crs[p] < ind) { if (vp[ crs[p] ].first <= p && p <= vp[ crs[p] ].second) { if (0 == token % t) { crs[p] += t - 1; ++def[p]; token = t - 1; } ++token; } ++crs[p]; } printf("%d\n", queryBIT(p) - def[p]); } } } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...23 7 2Attack 1 2Query 2Attack 2 3Query 2Attack 1 3Query 1Query 39 7 3Attack 5 5Attack 4 6Attack 3 7Attack 2 8Attack 1 9Query 5Query 3*******************************************************************************/