一點都不良心！！！！
AK 快樂
爆零快樂！！！
1、
A、 value 512mb 1s 規定一個區間的價值為這個區間中所有數 and 起來的值與這個區間所有數 or 起 來的值的乘積。 例如 3 個數 2,3,6。它們 and 起來的值為 2， or 起來的值為 7，這個區間對答 案的貢獻為 2*7=14。 現在有一個 n 個數的序列， 想知道所有 n*(n+1)/2 個區間的貢獻的和對 1000000007 取模後的結果是多少。 例如當這個序列為{3,4,5}時，那麼區間[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]的貢獻 分别為 9,0,0,16,20,25。 Input 第一行一個數 n 接下來一行 n 個數 ai，表示這 n 個數(0<=ai<=10^9)。 Output 一行表示答案。 3 4 5 70 limit %30 n<=1000 %100 n<=100000
我打的是nlog^2 拆位樹狀數組維護，f[i]表示區間i~現在循環到的點，的&值，g[i]表示|值。
然後記錄最後連續有多少個1或者0，然後區間修改f和g。。
【慢且錯 不說話。。
正解是，不用拆位，也是維護f,g,然後目前f和g的不同的值隻有logn個，并且是單調的，然後說可以用連結清單？[我覺得是單調隊列啊ORZ。。
這樣就nlogn了。。。
要不要放我的垃圾代碼：
View Code
真的好醜的code的說。。
2、
Sample Input
3 50
Sample Output
2
數位DP，數位DP，我打的數位DP太垃圾了，，又慢有錯ORZ。。
不會告訴你我現在還沒調出來，放棄治療。。。
大資料還是錯，應該是中間爆了吧ORZ。。。
233經過GDXB提點，終于AC了。。。。qpow爆了ORZ。。
無視我的調試真的好醜。。
3、
5 3
1 2
1 3
2 4
2 2
4 1
2 3
313
HINT
1<=P<=N
1<=K<=N
%30
N<=2000
Q<=2000
%100
N<=100000
Q<=100000
啊，可持久化。。。
就是先算b在a上面，這個直接算
然後就是b在c下面，那麼就是a->b->c這條鍊
然後對于dis[a,c]>=k 那麼b有k個位置
對于dis[a,c]<k 有dis[a,c]個位置
算出dfs序，然後就是詢問區間小于等于k的東西的值
我打的是字母樹。。。
啊啊啊資料開小了就 開心了！！真開心！！！
改資料範圍就A了smg！！！
垃圾的人生！！！坎坷！！！
2016-11-06 17:33:10