fork download
copy 
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "string.h"
  4. using namespace std;
  5.  
  6. #ifndef BYTE
  7. #define BYTE unsigned char
  8. #endif
  9.  
  10. #define _UNIT_SIZE       8
  11. #define _UNIT_POS        3
  12. const int UNIT_FULL_MASK=_UNIT_SIZE-1;
  13.  
  14. #define _COUNT_ARRAY_SIZE 256
  15.  
  16. const BYTE BYTE_ONE = 1;
  17.  
  18. int _countArray[_COUNT_ARRAY_SIZE];
  19. BYTE _one_bit_array[_UNIT_SIZE];
  20. BYTE _byteMaskArray[_UNIT_SIZE][_UNIT_SIZE];
  21.  
  22. const int *pCountArrayEnd = _countArray + _COUNT_ARRAY_SIZE;
  23. const BYTE *pOneBitArrayEnd = _one_bit_array + _UNIT_SIZE;
  24.  
  25. class ByteMethods
  26. {
  27. 	static void initCountArray()
  28.     {
  29.         int *p = _countArray;
  30.         BYTE i = 0;
  31.         while (p != pCountArrayEnd) {
  32.             int cnt = 0;
  33.             for (BYTE *p1 = _one_bit_array; p1 != pOneBitArrayEnd; ++p1) {
  34.                 if ((i & *p1) != 0) ++cnt;
  35.             }
  36.             *p = cnt;
  37.             ++i;
  38.             ++p;
  39.         }
  40.     }
  41.  
  42. 	static void initOneBitArray()
  43.     {
  44.         BYTE *p = _one_bit_array;
  45.         *p = BYTE_ONE;
  46.         BYTE *p1 = p + 1;
  47.         while (p1 != pOneBitArrayEnd) {
  48.             *p1 = *p << 1;
  49.             ++p1;
  50.             ++p;
  51.         }
  52.     }
  53.  
  54.     static void initByteMaskArray()
  55.     {
  56.         BYTE byteMask;
  57.         for (int left = 0; left < _UNIT_SIZE; ++left) {
  58.             _byteMaskArray[left][left] = byteMask = _one_bit_array[left];
  59.             for (int right = left+1; right < _UNIT_SIZE; ++right) {
  60.                 _byteMaskArray[left][right] = byteMask = byteMask | _one_bit_array[right];
  61.             }
  62.         }
  63.     }
  64.  
  65. public:
  66.     static void init()
  67.     {
  68.         initOneBitArray();
  69.         initCountArray();
  70.         initByteMaskArray();
  71.     }
  72.  
  73.     inline static int flipUnit(BYTE *p)
  74.     {
  75.         BYTE b1 = *p;
  76.         BYTE b2 = *p = ~b1;
  77.         return _countArray[b2] - _countArray[b1];
  78.     }
  79.  
  80.     inline static int flipUnitPart(BYTE *p, int startIndex, int endIndex)
  81.     {
  82.         BYTE b1 = *p;
  83.         BYTE mask = _byteMaskArray[startIndex][endIndex];      
  84.         BYTE b2 = *p = (b1 & ~mask) | (~b1 & mask);
  85.         return _countArray[b2] - _countArray[b1];
  86.     }
  87.  
  88.     inline static int getNumberOfTrue(BYTE b, int startIndex, int endIndex)
  89.     {
  90.         BYTE b2 = b & _byteMaskArray[startIndex][endIndex];
  91.         return _countArray[b2];
  92.     }
  93.  
  94.     inline static int *getCountArray() {
  95.         return _countArray;
  96.     }
  97. };
  98.  
  99. #define _ZERO_UNIT '\0'
  100.  
  101. #define _ARRAY_SIZE     32
  102. #define _NUMBER_OF_BITS _ARRAY_SIZE * _UNIT_SIZE
  103.  
  104. class BaseInterval
  105. {
  106. 	int  _size;
  107. 	int _numberOfUnits; 
  108. 	BYTE *_array;
  109. 	int  _numberOfTrue;
  110. 	bool _isNormal;
  111. 	int *_countArray;
  112.  
  113.     inline void flipAll()
  114.     {
  115.         BYTE *p    = _array;
  116.         BYTE *pEnd = p + _numberOfUnits;
  117.         while (p != pEnd) {
  118.             *p = ~*p;
  119.             ++p;
  120.         }
  121.     }
  122. public:
  123.     BaseInterval(): _size(0), _numberOfTrue(0), _isNormal(true)
  124.     {
  125.         _array     = new BYTE[_ARRAY_SIZE];
  126.         BYTE *p    = _array;
  127.         BYTE *pEnd = p + _ARRAY_SIZE;
  128.         while (p != pEnd) {
  129.             *p = _ZERO_UNIT;
  130.             ++p;
  131.         }
  132.         _countArray = ByteMethods::getCountArray();
  133.     }
  134.  
  135. 	~BaseInterval() { delete []_array; }
  136.  
  137.     static int getMaxSize()
  138.     {
  139.         return _NUMBER_OF_BITS;
  140.     }
  141.  
  142.     void set(const int size) {
  143.         _size  = size;
  144.         _numberOfUnits = _size >> _UNIT_POS;
  145.         int rem = _size & UNIT_FULL_MASK;
  146.         if (rem != 0) {
  147.             ++_numberOfUnits;
  148.         }
  149.     }
  150.  
  151.     inline void flip()
  152.     {
  153.         _isNormal = !_isNormal;
  154.         _numberOfTrue = _size - _numberOfTrue;
  155.     }
  156.  
  157.     inline void flip(const int startIndex, const int endIndex)
  158.     {
  159.         if (!_isNormal) {
  160.             flipAll();
  161.             _isNormal = true;
  162.         }
  163.  
  164.         int startIndex0    = startIndex >> _UNIT_POS;
  165.         int remStartIndex0 = startIndex &   UNIT_FULL_MASK;
  166.         int endIndex0      = endIndex   >> _UNIT_POS;
  167.         int remEndIndex0   = endIndex   &   UNIT_FULL_MASK;
  168.  
  169.         BYTE *p    = _array + startIndex0;
  170.         BYTE *pEnd = _array + endIndex0;
  171.         int cnt = 0;
  172.  
  173.         if (p == pEnd) {
  174.             cnt = ByteMethods::flipUnitPart(p, remStartIndex0, remEndIndex0);
  175.         } else {
  176.             cnt = ByteMethods::flipUnitPart(p, remStartIndex0, UNIT_FULL_MASK);
  177.             while (++p < pEnd) {
  178.                 cnt += ByteMethods::flipUnit(p);
  179.             }
  180.             cnt += ByteMethods::flipUnitPart(pEnd, 0, remEndIndex0);
  181.         }
  182.  
  183.         _numberOfTrue += cnt;
  184.     }
  185.  
  186.  
  187.     inline int getNumberOfTrue() const
  188.     {
  189.         return _numberOfTrue;
  190.     }
  191.  
  192.     inline int getNumberOfTrue(const int startIndex, const int endIndex)
  193.     {
  194.         if (!_isNormal) {
  195.             flipAll();
  196.             _isNormal = true;
  197.         }
  198.  
  199.         int startIndex0    = startIndex >> _UNIT_POS;
  200.         int remStartIndex0 = startIndex &   UNIT_FULL_MASK;
  201.         int endIndex0      = endIndex   >> _UNIT_POS;
  202.         int remEndIndex0   = endIndex   &   UNIT_FULL_MASK;
  203.  
  204.         BYTE *p    = _array + startIndex0;
  205.         BYTE *pEnd = _array + endIndex0;
  206.         int cnt = 0;
  207.  
  208.         if (p == pEnd) {
  209.             cnt = ByteMethods::getNumberOfTrue(*p, remStartIndex0, remEndIndex0);
  210.         } else {
  211.             cnt = ByteMethods::getNumberOfTrue(*p, remStartIndex0,  UNIT_FULL_MASK);
  212.             while (++p < pEnd) {
  213.                 cnt += _countArray[*p];
  214.             }
  215.             cnt += ByteMethods::getNumberOfTrue(*pEnd, 0, remEndIndex0);
  216.         }
  217.  
  218.         return cnt;
  219.     }
  220. };
  221.  
  222. class AggregateInterval
  223. {
  224. 	int  _size;
  225. 	int  _baseSize;
  226. 	int  _baseSize1;
  227. 	int  _rightShift;
  228. 	int  _mask;
  229. 	BaseInterval *_array;
  230.  
  231.     int set(int size)
  232.     {
  233.         _mask = _baseSize1 = _baseSize - 1;
  234.         _size  = size >> _rightShift;
  235.         int delta = size & _mask;
  236.         if (delta != 0) {
  237.             ++_size;
  238.         }
  239.         return delta;
  240.     }
  241.  
  242.     void allocate(int delta)
  243.     {
  244.         _array = new BaseInterval[_size];
  245.  
  246.         BaseInterval *p = _array;
  247.         BaseInterval *pEnd = _array + _size - 1;
  248.         while (p != pEnd) {
  249.             p->set(_baseSize);
  250.             ++p;
  251.         }
  252.         int size2 = (delta == 0) ? _baseSize : delta;
  253.         pEnd->set(size2);
  254.     }
  255.  
  256.     void setRightShift()
  257.     {
  258.         int nTemp = _baseSize;
  259.         _rightShift = 0;
  260.         while ((nTemp & 01) == 0) {
  261.             ++_rightShift;
  262.             nTemp = nTemp >> 1;
  263.         }
  264.     }
  265.  
  266. public:
  267. 	AggregateInterval(const int size) {
  268.         ByteMethods::init();
  269.  
  270.         _baseSize  = BaseInterval::getMaxSize();
  271.  
  272.         setRightShift();
  273.         int delta = set(size);
  274.         allocate(delta);
  275.     }
  276.  
  277.     ~AggregateInterval() { if (_size  > 0) delete []_array;  }
  278.  
  279.     inline void flip(const int startIndex, const int endIndex)
  280.     {	
  281.         int startIndex0    = startIndex >> _rightShift;
  282.         int remStartIndex0 = startIndex &  _mask;
  283.         int endIndex0      = endIndex   >> _rightShift;
  284.         int remEndIndex0   = endIndex   &  _mask;
  285.         BaseInterval *p    = _array + startIndex0;
  286.         BaseInterval *pEnd = _array + endIndex0;
  287.  
  288.         if (p == pEnd) {
  289.             p->flip(remStartIndex0, remEndIndex0);
  290.         } else {
  291.             p->flip(remStartIndex0, _baseSize1);
  292.             while (++p < pEnd) {
  293.                 p->flip();
  294.             }
  295.             pEnd->flip(0, remEndIndex0);
  296.         }
  297.     }
  298.  
  299.     inline int getNumberOfTrue(const int startIndex, const int endIndex) const
  300.     {
  301.         int startIndex0    = startIndex >> _rightShift;
  302.         int remStartIndex0 = startIndex &  _mask;
  303.         int endIndex0      = endIndex   >> _rightShift;
  304.         int remEndIndex0   = endIndex   &  _mask;
  305.         BaseInterval *p    = _array + startIndex0;
  306.         BaseInterval *pEnd = _array + endIndex0;
  307.  
  308.         int cnt;
  309.         if (p == pEnd) {
  310.             cnt = p->getNumberOfTrue(remStartIndex0, remEndIndex0);
  311.         } else {
  312.             cnt = p->getNumberOfTrue(remStartIndex0, _baseSize1);
  313.             while (++p < pEnd) {
  314.                 cnt += p->getNumberOfTrue();
  315.             }
  316.             cnt += pEnd->getNumberOfTrue(0, remEndIndex0);
  317.         }
  318.  
  319.         return cnt;
  320.     }
  321. };
  322.  
  323.  
  324. #define BUF 4096
  325. char ibuf[BUF];
  326.  
  327. int ipt = BUF;
  328.  
  329. int readInt() {
  330.  
  331.     while (ipt < BUF && ibuf[ipt] < '0') ipt++;
  332.  
  333.     if (ipt == BUF) {
  334. 	fread(ibuf, 1, BUF, stdin);
  335.  
  336. 	ipt = 0;
  337. 	while (ipt < BUF && ibuf[ipt] < '0') ipt++;
  338.  
  339.     }
  340.     int n = 0;
  341.     while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
  342.  
  343.     if (ipt == BUF) {
  344. 	fread(ibuf, 1, BUF, stdin);
  345.  
  346. 	ipt = 0;
  347. 	while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
  348.  
  349.     }
  350.     return n;
  351. }
  352.  
  353.  
  354. int main()
  355. {
  356.     int n, q;
  357.    // char line[100];
  358.     //setvbuf(stdin , NULL, _IOFBF, 1000000);
  359.     //setvbuf(stdout, NULL, _IOFBF, 1000000);
  360.  
  361.    // gets(line);
  362. 	//sscanf(line, "%d %d", &n, &q);
  363.      n = readInt();
  364.      q = readInt();
  365.     AggregateInterval interval(n);
  366.     int op, startIndex, endIndex, cnt;
  367.     char *p;
  368.     for (int i = 0; i < q; i++) {
  369.         //gets(line);
  370.         //p = line;
  371.         op         = readInt();
  372.         startIndex =readInt();
  373.         endIndex   = readInt();
  374.  
  375.         if (op == 0) {
  376.             interval.flip(startIndex, endIndex);
  377.         } else {
  378.             cnt = interval.getNumberOfTrue(startIndex, endIndex);
  379.             printf("%d\n", cnt);
  380.         }
  381.     }
  382. }  
  383.  
  384.  
Runtime error #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cq0dPj
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!