Problem Description In mathematics and computer science, an algorithm describes a set of procedures or instructions that define a procedure. The term has become increasing popular since the advent of cheap and reliable computers. Many companies now employ a single coder to write an algorithm that will replace many other employees. An added benefit to the employer is that the coder will also become redundant once their work is done. 1
9 add 1 add 2 add 3 add 4 add 5 sum add 6 del 3 sum 6 add 1 add 3 add 5 add 7 add 9 sum
3 4 5 HintC++ maybe run faster than G++ in this problem.
/**
hdu4288 離線線段樹
題目大意：對一個起初為空的數組進行三種操作：add x：插入x：del x：刪除x：sum ：查詢在當前數列中下標對5取模為3的數的總和。
解題思路：暴力會超時。可以利用線段樹來做，由於線段樹不支持點的刪除和增加，普通的在線線段樹無法滿足題目要求。我們可以把所有的在輸入中增加過的點全部存上，
然後去重，組成一個序列，對於其中的元素如果當前線段樹中有，那麼就標記為1，否則為0，維護線段樹中標記的個數cnt，以及對5取模的五種情況的值。
遇到添加、刪除操作的時候，只要把那個節點的值改變，然後將它對下標的影響處理好就可以。
那麼如何處理這些操作對下標的影響呢？
現在我們考慮一個父區間，假設它的左右子區間已經更新完畢。
顯然，左區間中下標%5的情況與父區間中%5的情況完全相同；
可是，右區間中卻不一定相同，因為右區間中的下標是以 mid 當作 1 開始的。
那麼，只要我們知道左區間中有效元素的個數 cnt，我們就能知道右區間中的下標 i 在父區間中對應的下標為 i+cnt。
所以，雖然我們最終要的只是總區間中下標%5 = 3的和。但是在更新時我們需要知道右區間%5的所有情況。
於是我們要在線段樹的每個節點開一個 sum[5] 和一個 cnt，分別記錄這個節點中下標%5的5種情況的和與有效元素的個數。
而查詢時，直接訪問總區間的 sum[3] 即可。
*/
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=500000+10;
int n,len,flag;
char str[maxn][10];
int num[maxn],s[maxn];
struct node
{
int l,r,cnt;
LL sum[5];
}tree[maxn*4];
void init(int l,int r,int i)
{
tree[i].l=l;
tree[i].r=r;
tree[i].cnt=0;
memset(tree[i].sum,0,sizeof(tree[i].sum));
if(l!=r)
{
int mid=(l+r)>>1;
init(l,mid,i<<1);
init(mid+1,r,2*i+1);
}
}
void add(int x)
{
for(int i=0;i<5;i++)
{
int j=(i+tree[x<<1].cnt)%5;
tree[x].sum[j]=tree[x<<1].sum[j]+tree[x<<1|1].sum[i];
}
}
void insert(int i,int pos,int m)
{
flag?tree[i].cnt++:tree[i].cnt--;
if(tree[i].l==tree[i].r)
{
tree[i].sum[1]=flag*m;
return;
}
int mid=(tree[i].l+tree[i].r)>>1;
if(pos<=mid)
insert(i<<1,pos,m);
else
insert(i<<1|1,pos,m);
add(i);
}
int main()
{
while(~scanf(%d,&n))
{
len=0;
for(int i=0;i
Problem Description
In mathematics and computer science, an algorithm describes a set of procedures or instructions that define a procedure. The term has become increasing popular since the advent of cheap and reliable computers. Many companies now employ a single coder to write
an algorithm that will replace many other employees. An added benefit to the employer is that the coder will also become redundant once their work is done. 1
You are now the signle coder, and have been assigned a new task writing code, since your boss would like to replace many other employees (and you when you become redundant once your task is complete).
Your code should be able to complete a task to replace these employees who do nothing all day but eating: make the digest sum.
By saying “digest sum” we study some properties of data. For the sake of simplicity, our data is a set of integers. Your code should give response to following operations:
1. add x – add the element x to the set;
2. del x – remove the element x from the set;
3. sum – find the digest sum of the set. The digest sum should be understood by9
add 1
add 2
add 3
add 4
add 5
sum
add 6
del 3
sum
6
add 1
add 3
add 5
add 7
add 9
sum
Sample Output
3
4
5
HintC++ maybe run faster than G++ in this problem.
