树状数组

作者: 编程技术  发布:2019-09-20

能够达成基本操作:

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)     Special Judge

1、给定 i ,x . 给 bit[i] 加上 x

Problem Description

      Most modern archivers, such as WinRAR or WinZIP, use modifications of Lempel-Ziv method as their primary compression algorithm. Although decompression of LZ-compressed archives is usually easy and fast, the compression process itself is often rather complicated and slow. Therefore professional archivers use approximation methods that sometimes do not allow to achieve the best possible compression. 

      This situation doesn’t satisfy your chief George. He would like to create the best archiver WinGOR. The archiver will use the following modification of LZ77 algorithm.
      The text is partitioned to chunks of length not exceeding 4096. Each chunk is compressed independently. We will describe the decompression of one chunk t. Based on this description, you will have to create a compression algorithm that will create the shortest possible compressed chunk x from the given chunk t.
      The compressed chunk is written down as the sequence of plain characters and repetition blocks. Plain character is 8 bits long. When decompressing, plain character c is simply copied to output. Repetition block (r; l) consists of two parts: reference r and length l, each 12 bits long. Reference r is an integer number between 1 and 4095. When repetition block (r; l) is obtained after decompressing i − 1 characters of text, characters t[i − r ... i − r + l − 1] are copied to output. Note, that r can be less than l, in this
case recently copied characters are copied to output as well.

      To help decompressor distinguish between plain characters and repetition blocks a leading bit is prepended to each element of the compressed text: 0 means plain character follows, 1 — repetition block follows. 

      For example, “aaabbaaabababababab” can be compressed as “aaabb(5,4)(2,10)”. The compressed variant has 8 + 8 + 8 + 8 + 8 + 24 + 24 + 7 = 95 bits instead of 152 in the original text (additional 7 bits are used to distinguish between plain characters and repetition blocks).
      Given a text chunk, find its compressed representation which needs fewest number of bits to encode

2、给定 l , r . 求出 bit[l] +...+ bit[r]

Input

      Input file contains a text chunk t. Its length doesn’t exceed

  1. A text chunk contains only small letters of the English alphabet.

图片 1图片 2

Output

      Print the length of the compressed text in bits at the first line of the output file. Print the compressed chunk itself at the second line of the output file. Use characters themselves to denote plain characters and “(r,l)” notation (without spaces) to denote repetition blocks.

#include<iostream>#include<cmath>#include<cstdio>using namespace std;const int maxn = 1e6 + 10;#define int long longint bit[maxn];int n, q;int lowbit(int i){    return i&(-i);}long long getsum(int i){   //bit[1]+...+bit[i]  前缀和    long long res = 0;    while (i >0 ){        res += bit[i];        i -= lowbit;    }    return res;}void add(int i, int x){    //在bit[i]上加上x    while (i <=n){        bit[i] += x;        i += lowbit;    }}int main(){    cin >> n >> q;    //n和数,q次查询    int z;    for (int i = 1; i <= n; i++){        cin >> z;        add;    }    int a,b,c;    while (q--){                cin >> a >> b >> c;        if (a == 1){            add;        }        else if(a == 2){            cout << getsum-getsum(b-1) << endl;        }    }    return 0;}

Sample Input

aaabbaaabababababab 

View Code

Sample Output

95 

aaabb(5,4)(2,10)

题意概述

给定一种压缩准则:或直接复制,或将重新出现的字符用二元数对(r,l)表示,代表[i − r ... i − r + l − 1]界定内的字符串。当中央市直机关接复制的字符占9位,每一种二元数对占二十二个人。对于给定的待压缩字符串,要求输出压缩后的微小数据位数和裁减后的编码。

分析

轻易看到,字符串中前i位怎么着编码,对后继字符串的编码是从未有过影响的。那样,我们就足以想到利用保存决策的动态规划进行编码。 这里须求的一点小trick在于怎么样寻找尽量靠前的一段最长重复子串。代入kmp算法的思绪,大家能够对原字符串的每一段后缀预管理出next数组,那样原字符串中种种前缀的最长重复子串就足以在O(n)的光阴内获取了。于是这里能够得出二个叶影参差度O(n^2)的动态规划: 记minbit[i]为压缩前i个字符所需的矮小数据量,str[i]为那儿的裁决,r[i],l[i]为此番改动时压缩成的数对(若不需降低,str[i]=i, r[i]存款和储蓄不需减少的片段的初阶点) 那么,每一回改造时就足以从0到i-1枚举决策j,选择能够使(minbit[j] + (i-j)*9)或minbit[i - next[j][i-1]] + 25获得最小值的j,并保存决策。最终能够因而一个递归函数推出最终答案。 (这里供给注意一点难题……next数组是二维的,数据范围maxn为2^12,而内部存款和储蓄器限制为6伍仟KB……假若用next[maxn][maxn]的法子开数组显明会MLE……所以自身鼓起勇气采纳了动态内部存款和储蓄器分配……)

 AC代码

 1 //Verdict: Accepted

 2 // Submission Date: 2014-10-02 16:34:32
 3 // Time: 8256MS
 4 // Memory: 34624KB
 5
 6 /*=============================================================================================================================*/
 7 /*======================================================Code by Asm.Def========================================================*/
 8 /*=============================================================================================================================*/
 9 #include <cstdio>
10 #include <iostream>
11 #include <algorithm>
12 #include <cmath>
13 #include <cctype>
14 #include <memory.h>
15 #include <cstring>
16 #include <cstdlib>
17 using namespace std;
18 #define maxn ((int)4.1e3)
19 /*===========================================================TYPES=============================================================*/
20 typedef long long LL;
21   
22 /*======================================================GLOBAL VARIABLES=======================================================*/
23 char ch[maxn];
24 int len = 0, minbit[maxn], *next[maxn];
25 int l[maxn], r[maxn], str[maxn];
26 /*==========================================================FUNCTIONS==========================================================*/
27 inline void getnext(int l){
28     int i, j, L = len - l;
29     next[l] = new int[L+2];
30     int *Next = next[l];
31     Next[0] = 0;
32     for(i = 1;i < L;++i){
33         j = Next[i-1] - 1;
34         while(ch[l+i] != ch[l+j+1] && j >= 0)
35             j = Next[j] - 1;
36         if(ch[l+i] == ch[l+j+1])
37             Next[i] = j + 2;
38         else Next[i] = 0;
39     }
40 }
41 void printpro(int i){
42     if(str[i] == i){
43         if(r[i])printpro(r[i]-1);
44         int j;
45         for(j = r[i];j <= i;++j)putchar(ch[j]);
46         return;
47     }
48     printpro(str[i]);
49     printf("(%d,%d)", r[i], l[i]);
50 }
51 int main(){
52     #ifdef DEBUG
53     assert(freopen("test","r",stdin));
54     #endif
55     //--------------------------------------------------variables-----------------------------------------------------------
56       
57     //-----------------------------------------------------work-------------------------------------------------------------
58     char c;
59     while(isalpha(c = getchar()))str[len] = len, ch[len++] = c;
60     int i, j, Min, t;
61     for(i = 0;i < len - 1; ++i)
62         getnext(i);
63     minbit[0] = 9;
64     for(i = 1;i < len; ++i){
65         Min = 0x7fffffff;
66         for(j = 0;j < i;++j)
67             if(minbit[j] + (i-j)*9 < Min){
68                 Min = minbit[j] + (i-j)*9;
69                 str[i] = i;
70                 r[i] = j+1;
71             }
72         for(j = 0;j < i; ++j){
73             t = next[j][i-j];
74             if(!t)continue;
75             if(minbit[i-t] + 25 < Min){
76                 Min = minbit[i-t] + 25;
77                 str[i] = i-t;
78                 r[i] = i+1-t-j;
79                 l[i] = t;
80             }
81         }
82         minbit[i] = Min;
83     }
84     printf("%dn", minbit[len-1]);
85     printpro(len-1);
86     return 0;
87 }
88 /*=============================================================================================================================*/

 

 

本文由贝博体育app发布于编程技术,转载请注明出处:树状数组

关键词:

上一篇:没有了
下一篇:洛谷P4065 [JXOI2017]颜色(线段树)