[POJ] 3468. A Simple Problem with Integers

題目連結:http://poj.org/problem?id=3468
裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ 
#include <iostream>
#include <utility>
using namespace std;
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second

const int N = 100000 + 5;

class SegTree{
	private:
		PLL nodes[N<<2];
		int size;
		inline int lc(int x){return (x<<1)+1;}
		inline int rc(int x){return (x<<1)+2;}
		inline void push(int l, int r, int id){
			if(r-l>1){
				nodes[lc(id)].FF += nodes[id].FF;
				nodes[rc(id)].FF += nodes[id].FF;
			}
			nodes[id].SS += nodes[id].FF * (r-l);
			nodes[id].FF=0;
		}
		inline void pull(int l, int r,int id){
			int mid=(l+r)>>1;
			lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l);
			lld rr = nodes[rc(id)].SS+nodes[rc(id)].FF*(r-mid);
			nodes[id].SS = ll + rr;
		}
		template<typename T>
		void build(T* arr, int l, int r, int id){
			nodes[id].FF=0;
			if(r-l==1){
				nodes[id].SS = arr[l];
			}else{
				int mid=(l+r)>>1;
				build(arr, l, mid, lc(id));
				build(arr, mid, r, rc(id));
				nodes[id].SS = nodes[lc(id)].SS+nodes[rc(id)].SS;
			}
		}
		lld query(int ql, int qr, int l, int r, int id){
			if(r <= ql or qr <= l) return 0;
			push(l,r,id);
			if(ql <= l and r <= qr) return nodes[id].SS;
			int mid=(l+r)>>1;
			return query(ql, qr, l, mid, lc(id))+query(ql, qr, mid, r, rc(id));
		}
		void modify(int ql, int qr, int l, int r, int v, int id){
			if(r <= ql or qr <= l) return;
			push(l, r, id);
			if(ql <= l and r <= qr){
				nodes[id].FF = v;
				return;
			}
			int mid=(l+r)>>1;
			modify(ql, qr, l, mid, v, lc(id));
			modify(ql, qr, mid, r, v, rc(id));
			pull(l, r, id);
		}
	public:
		template<typename T>
		void build(T* arr, int n){
			size=n;
			build(arr, 0, n, 0);
		}
		lld query(int l,int r){
			return query(l, r, 0, size, 0);
		}
		void modify(int l, int r, int v){
			modify(l, r, 0, size, v, 0);
		}
} seg;

int arr[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>arr[i];
	seg.build(arr,n);
	while(q--){
		char type;cin>>type;
		if(type=='C'){
			int l, r, v;cin>>l>>r>>v;
			seg.modify(l-1,r,v);
		}else if(type=='Q'){
			int l, r;cin>>l>>r;
			cout<<seg.query(l-1,r)<<'\n';
		}
	}
	return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(...
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容

[Codeforces] 731F. Video Cards

題目連結: http://codeforces.com/problemset/problem/731/F 惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況，而計算時就是要算$[ik, i(k+1))$的數字數有幾個，因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法)，所以就照著做囉(? #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; lld sum[N]; bool isok[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum[x]++; isok[x]=1; } for(int i=1;i<N;i++) sum[i]+=sum[i-1]; lld ans = 0; for(int i=1;i<N;i++){ if(!isok[i]) continue; lld cur = 0; for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]); ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }
閱讀完整內容